# Heap

Invented by Williams (1964) 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$ very easy implementation two heaps cannot be easily merged priority_queue in C++ STL, java.util.PriorityQueue in Java, or heapq module in Python