#algorithm #data-structure #tree #leetcode

idea

A heap is a complete tree (often binary), where the root is always larger (in the case of a max heap) or smaller (in the case of a min-heap) than its nodes. A max heap:

    graph TD;

    10 → 6;
    10 → 4;
    4 → 3;
    6 → 5;
    6 → 1;

Insertion and deletion from heaps are done in $O(log(n))$, making it a potential better candidate than arrays or linked list which require consistent insertion and retrieval time.

Retrieving max/min from heap is done in $O(1)$

heapify - build a heap from an array in place

Heapify is recursive.

1. Start from root
2. Heapify each child (for binary trees, $heapify(array, 2n)$ and $heapify(2n+1)$)
3. Look at child nodes. Sift down the current root to its correct place.

Sift down:

1. Set root is the element to sift.
2. Compare root with the max of root and its children.
3. Swap to have the largest of the three as root. Sift down using the element to sift.

insert in Heap

1. Add node as bottomest leaf.
2. Sift up

Sift up: Similar to sift down, but root element is the parent of the node to sift, then we move up till node is in its place. We don't need to compare to sibling because it's smaller.

Delete in Heap

1. Swap node to delete and last node.
2. Remove last node.
3. Sift down the swapped element.

links

Heap sort

references

https://en.wikipedia.org/wiki/Heap_(data_structure)

https://catherine-leung.gitbook.io/data-strutures-and-algorithms/sorting/heap-and-heap-sort/heap-sort

https://leetcode.com/explore/featured/card/heap/643/heap/4018/

reference implementation for Heapify

function heapify(array, root = 0) {
  if (root >= array.length / 2) {
    return
  }
  const c1 = root * 2 + 1
  const c2 = root * 2 + 2
  heapify(array, c1)
  heapify(array, c2)
  siftDown(array, root, array.length)
}

function siftDown(array, root, size) {
  let rootVal = array[root];

  while (true) {
    const c1 = root * 2 + 1
    const c2 = root * 2 + 2
    const val1 = c1 < size ? array[c1] : Number.MIN_SAFE_INTEGER
    const val2 = c2 < size ? array[c2] : Number.MIN_SAFE_INTEGER
    if (val1 > val2 && val1 > rootVal) {
      swap(array, root, c1)
      root = c1
    } else if (val2 > rootVal) {
      swap(array, root, c2)
      root = c2
    } else {
      // elmt in its place
      break;
    }
  }
}

function swap(array, i, j) {
  const tmp = array[i]
  array[i] = array[j]
  array[j] = tmp
}

function displayTree(array, index, level) {
  if (index >= array.length) {
    return
  }
  let res = ""
  for (let i = 0; i < level; i++) {
    res = `${res}  |`
  }
  console.log(`${res}__${array[index]}`)
  displayTree(array, index * 2 + 1, level + 1)
  displayTree(array, index * 2 + 2, level + 1)
}

const array = [3, 4, 1, 5, 34, 21, 454, 12, 66, 23, 34, 55, 2, 5, 6, 2, 9, 7]
heapify(array)
displayTree(array, 0, 1)

Insert and delete and sift up

function getSiblingIndex(elem) {
  return isLeft(elem) ? elem + 1 : elem - 1
}

function isLeft(elem) {
  return elem % 2 === 1
}

function siftUp(array, elemIndex) {
  while (elemIndex > 0) {
    const rootIndex = getParentIndex(elemIndex)
    const rootVal = array[rootIndex]
    const elemVal = array[elemIndex]
    if (elemVal > rootVal) {
      swap(array, rootIndex, elemIndex)
      elemIndex = rootIndex
    } else {
      // elmt in its place
      break;
    }
  }
}

function insert(array, element) {
  array.push(element)
  siftUp(array, array.length - 1)
}

function deleteFromHeap(array, elementIndex) {
  swap(array, elementIndex, array.length - 1)
  array.pop()
  siftDown(array, elementIndex, array.length)
}