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