Heap

Invented by Williams (1964)
Idea:
  • heap is a full binary tree with a heap ordering: the priority of each node is higher then the priorities of its children
  • root is the node with the highest priority
  • when inserting / deleting an item, the heap ordering is violated only locally; it suffices to “bubble” a given node up or down
  • all the nodes can be stored in an array so that children of the \(i\)-th node are at positions \(2i\) and \(2i + 1\)
Advantages: very easy implementation
Disadvantages: two heaps cannot be easily merged
Implementation: priority_queue in C++ STL, java.util.PriorityQueue in Java, or heapq module in Python
[You can download the application for offline viewing.]

References

  • J.W.J. Williams. Algorithm 232: heapsort. Communications of the ACM, 7(6):347-348, 1964. [bib]