algoalgo-world
algoalgo-world/tree/build-heap
tree/build-heap

Build Heap

kind
complete binary tree, max-heap
ordering
parent over child only, left and right mean nothing
time
O(n)
space
O(1)
height when done
log2 n
per node
nothing

it starts from a tree that is already standing. building the same heap one value at a time costs n log n, this costs n

pick a language to open the code

def heapify(a, end, root):
    biggest = root
    left = 2 * root + 1
    right = 2 * root + 2
    if left < end and a[left] > a[biggest]:
        biggest = left
    if right < end and a[right] > a[biggest]:
        biggest = right
    if biggest != root:
        a[root], a[biggest] = a[biggest], a[root]
        heapify(a, end, biggest)


def build_heap(a):
    for root in range(len(a) // 2 - 1, -1, -1):
        heapify(a, len(a), root)
function heapify(a, end, root) {
  let biggest = root;
  const left = 2 * root + 1;
  const right = 2 * root + 2;
  if (left < end && a[left] > a[biggest]) biggest = left;
  if (right < end && a[right] > a[biggest]) biggest = right;
  if (biggest === root) return;
  [a[root], a[biggest]] = [a[biggest], a[root]];
  heapify(a, end, biggest);
}

function buildHeap(a) {
  for (let root = (a.length >> 1) - 1; root >= 0; root--) {
    heapify(a, a.length, root);
  }
}
static void heapify(int a[], int end, int root) {
    int biggest = root;
    int left = 2 * root + 1;
    int right = 2 * root + 2;
    if (left < end && a[left] > a[biggest]) biggest = left;
    if (right < end && a[right] > a[biggest]) biggest = right;
    if (biggest == root) return;
    int t = a[root];
    a[root] = a[biggest];
    a[biggest] = t;
    heapify(a, end, biggest);
}

void build_heap(int a[], int n) {
    for (int root = n / 2 - 1; root >= 0; root--) heapify(a, n, root);
}
void heapify(std::vector<int>& a, int end, int root) {
    int biggest = root;
    int left = 2 * root + 1;
    int right = 2 * root + 2;
    if (left < end && a[left] > a[biggest]) biggest = left;
    if (right < end && a[right] > a[biggest]) biggest = right;
    if (biggest == root) return;
    std::swap(a[root], a[biggest]);
    heapify(a, end, biggest);
}

void build_heap(std::vector<int>& a) {
    int n = static_cast<int>(a.size());
    for (int root = n / 2 - 1; root >= 0; root--) heapify(a, n, root);
}
static void Heapify(int[] a, int end, int root) {
    int biggest = root;
    int left = 2 * root + 1;
    int right = 2 * root + 2;
    if (left < end && a[left] > a[biggest]) biggest = left;
    if (right < end && a[right] > a[biggest]) biggest = right;
    if (biggest == root) return;
    (a[root], a[biggest]) = (a[biggest], a[root]);
    Heapify(a, end, biggest);
}

static void BuildHeap(int[] a) {
    for (int root = a.Length / 2 - 1; root >= 0; root--) {
        Heapify(a, a.Length, root);
    }
}
static void heapify(int[] a, int end, int root) {
    int biggest = root;
    int left = 2 * root + 1;
    int right = 2 * root + 2;
    if (left < end && a[left] > a[biggest]) biggest = left;
    if (right < end && a[right] > a[biggest]) biggest = right;
    if (biggest == root) return;
    int t = a[root];
    a[root] = a[biggest];
    a[biggest] = t;
    heapify(a, end, biggest);
}

static void buildHeap(int[] a) {
    for (int root = a.length / 2 - 1; root >= 0; root--) {
        heapify(a, a.length, root);
    }
}
watch it run, then read it