Programmer's Wiki
Advertisement

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

Advertisement