Heap (data structure)

tree-based data structure in computer science

In computer science, a heap is a type of tree (data structure) that satisfies the heap property. Heaps are useful when you need to remove the item with the highest (or lowest) value.[1] A common implementation of a heap is the binary heap in which the tree is a complete binary tree.

Example of a binary max-heap containing items between 1 and 100.

Heap property

change
  • In a max-heap, the value of each item is less than or equal to the value of its parent, with the maximum-value item at the root.[1]
  • In a min-heap, the value of each item is greater than or equal to the value of its parent, with the minimum-value item at the root.[1]

Operations

change
  • find: return a maximum item of a max-heap or a minimum item of a min-heap.
  • insert: add a new item to the heap.
  • extract: returns the maximum item from a max-heap (or minimum item from a min-heap) after removing it.
  • delete: removes the root of a max-heap (or min-heap).
  • size: return the number of items in the heap.
  • is-empty: return true if the heap is empty, false otherwise.

Maintaining the heap property

change
  • insert: insert the item at the bottom rightmost location; swap the item with its parent until the heap property is preserved.
  • delete: remove the root; swap it with the item at the bottom rightmost location; swap the new root downwards with the smaller of its children (for a min-heap) until the heap property is preserved.

References

change
  1. 1.0 1.1 1.2 Adamchik, Victor. "Binary Heap". Computer Science - 121 Fall 2009. CMU. Archived from the original on 25 April 2020. Retrieved 11 October 2020.