| 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 |