Binary Heap

pick a language to open the code

def sift_up(heap, at):
    while at > 0:
        parent = (at - 1) // 2
        if heap[parent] >= heap[at]:
            return
        heap[parent], heap[at] = heap[at], heap[parent]
        at = parent


def sift_down(heap, at):
    while True:
        child = 2 * at + 1
        if child >= len(heap):
            return
        if child + 1 < len(heap) and heap[child] < heap[child + 1]:
            child += 1
        if heap[at] >= heap[child]:
            return
        heap[at], heap[child] = heap[child], heap[at]
        at = child


def push(heap, value):
    heap.append(value)
    sift_up(heap, len(heap) - 1)


def pop(heap):
    top = heap[0]
    last = heap.pop()
    if heap:
        heap[0] = last
        sift_down(heap, 0)
    return top

function siftUp(heap, at) {
  while (at > 0) {
    const parent = (at - 1) >> 1;
    if (heap[parent] >= heap[at]) return;
    [heap[parent], heap[at]] = [heap[at], heap[parent]];
    at = parent;
  }
}

function siftDown(heap, at) {
  for (;;) {
    let child = 2 * at + 1;
    if (child >= heap.length) return;
    if (child + 1 < heap.length && heap[child] < heap[child + 1]) child++;
    if (heap[at] >= heap[child]) return;
    [heap[at], heap[child]] = [heap[child], heap[at]];
    at = child;
  }
}

function push(heap, value) {
  heap.push(value);
  siftUp(heap, heap.length - 1);
}

function pop(heap) {
  const top = heap[0];
  const last = heap.pop();
  if (heap.length > 0) {
    heap[0] = last;
    siftDown(heap, 0);
  }
  return top;
}

static void swap(int a[], int i, int j) {
    int t = a[i];
    a[i] = a[j];
    a[j] = t;
}

static void sift_up(int heap[], int at) {
    while (at > 0 && heap[(at - 1) / 2] < heap[at]) {
        swap(heap, (at - 1) / 2, at);
        at = (at - 1) / 2;
    }
}

static void sift_down(int heap[], int size, int at) {
    for (;;) {
        int child = 2 * at + 1;
        if (child >= size) return;
        if (child + 1 < size && heap[child] < heap[child + 1]) child++;
        if (heap[at] >= heap[child]) return;
        swap(heap, at, child);
        at = child;
    }
}

int push(int heap[], int size, int value) {
    heap[size] = value;
    sift_up(heap, size);
    return size + 1;
}

int pop(int heap[], int size, int* top) {
    *top = heap[0];
    heap[0] = heap[size - 1];
    sift_down(heap, size - 1, 0);
    return size - 1;
}

void sift_up(std::vector<int>& heap, int at) {
    while (at > 0 && heap[(at - 1) / 2] < heap[at]) {
        std::swap(heap[(at - 1) / 2], heap[at]);
        at = (at - 1) / 2;
    }
}

void sift_down(std::vector<int>& heap, int at) {
    int size = static_cast<int>(heap.size());
    for (;;) {
        int child = 2 * at + 1;
        if (child >= size) return;
        if (child + 1 < size && heap[child] < heap[child + 1]) child++;
        if (heap[at] >= heap[child]) return;
        std::swap(heap[at], heap[child]);
        at = child;
    }
}

void push(std::vector<int>& heap, int value) {
    heap.push_back(value);
    sift_up(heap, static_cast<int>(heap.size()) - 1);
}

int pop(std::vector<int>& heap) {
    int top = heap.front();
    heap.front() = heap.back();
    heap.pop_back();
    if (!heap.empty()) sift_down(heap, 0);
    return top;
}

class MaxHeap {
    readonly List<int> items = new List<int>();

    public int Count => items.Count;

    public void Push(int value) {
        items.Add(value);
        int at = items.Count - 1;
        while (at > 0) {
            int parent = (at - 1) / 2;
            if (items[parent] >= items[at]) return;
            (items[parent], items[at]) = (items[at], items[parent]);
            at = parent;
        }
    }

    public int Pop() {
        int top = items[0];
        items[0] = items[items.Count - 1];
        items.RemoveAt(items.Count - 1);
        int size = items.Count;
        int at = 0;
        while (true) {
            int child = 2 * at + 1;
            if (child >= size) return top;
            if (child + 1 < size && items[child] < items[child + 1]) child++;
            if (items[at] >= items[child]) return top;
            (items[at], items[child]) = (items[child], items[at]);
            at = child;
        }
    }
}

static class MaxHeap {
    private final int[] items;
    private int size;

    MaxHeap(int room) { items = new int[room]; }

    void push(int value) {
        items[size++] = value;
        int at = size - 1;
        while (at > 0 && items[(at - 1) / 2] < items[at]) {
            swap((at - 1) / 2, at);
            at = (at - 1) / 2;
        }
    }

    int pop() {
        int top = items[0];
        items[0] = items[--size];
        int at = 0;
        while (true) {
            int child = 2 * at + 1;
            if (child >= size) return top;
            if (child + 1 < size && items[child] < items[child + 1]) child++;
            if (items[at] >= items[child]) return top;
            swap(at, child);
            at = child;
        }
    }

    private void swap(int i, int j) {
        int t = items[i];
        items[i] = items[j];
        items[j] = t;
    }
}