A heap is a tree data structure where each node's data is greater than any of its children. Heaps are commonly used as priority queues.

Operations

Common operations on a heap include:

• Deleting the greatest value in the heap, which is always the root node.
• Updating a value within the heap.
• Inserting a value to the heap.
• Merging two heaps.

Heap sort

A heap sort is carried out by inserting all the items from a list into a heap. The sorted list can then be created by taking the root node and appending it into a list until the heap is empty.

Variants

• 2-3 heap
• Beap
• Binary heap
• Binomial heap
• D-ary heap
• Fibonacci heap
• Leftist heap
• Pairing heap
• Skew heap
• Soft heap
• Ternary heap
• Treap

See also

• heapsort

External links

• Heap on Wikipedia