Heap

A heap is a special type of tree with the property that every node is larger than its children. If every node is smaller than its children the heap is referred to as a min-heap. The most common type of heap is a binary heap, but fibonacci heaps give better complexity.

Due to this property heaps are very useful for priority queues, the node with the highest priority will always be the root node.

Operation Complexity Description
peek $O(1)$ returns value at the top of the heap
pop $O(\log n)$ removes the node at the top of the heap
push $O(\log n)$ inserts a node in its proper place in the heap
find $O(n)$ it is possible that the entire heap must be searched

Coming soon…

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License