Binary tree with two additional constraints:

  1. Shape property: complete binary tree.
  2. Heap property: the key stored in each node is greater or equal(max-heaps) to or less than or equal to(min-heaps) the keys in the node’s children, according to some total order.

Heap operations⌗

Insert⌗

Steps to add an element to a heap:

  1. Add element to the bottom level of the heap at the leftmost open space.
  2. Compare to its parent, if they are in the correct the order, stop.
  3. If not, swap element with its parent and return to the previous step.

Extract: Delete the root from heap⌗

  1. Replace the root of heap with the last element on the bottom level.
  2. Compare the new root with its children; if they are in the correct order, stop.
  3. If not, swap the element with one of its children and return to the previous step.

Delete⌗

Decrease or increase key⌗

Heap implementation with array⌗

each element a at index i has

  • children at indices 2i + 1 and 2i + 2.
  • Its parent at index floor((i - 1) / 2).