Introduction

Learning to Love Heaps

Heapify All The Things With Heap Sort

• heaps are a great example of many core computer science concepts working together in order to form one very large abstraction, which is made up of smaller parts that we’re already familiar with
• a heap is basically just a binary tree with 2 more specifications:
  • shape - a heap must be a complete tree
    • so all the levels of the tree must be completely filled, except maybe the last one
    • the last level must have the left-most nodes filled, always!
  • order - root properties
    • min-heap ⇒ root node must have all of it’s children be either greater than or equal to its children
    • max-heap ⇒ root node must have all of it’s children be either less than or equal to its children
• in the context of algorithm interviews, heaps and priority queues can be treated as the same data structure

Types

Binary Heap

• a binary tree that satisfies the heap property

Max Binary Heap

• has the greatest value at the top
• the value of every node must be greatest among the node values in its entire subtree.

Min Binary Heap

• has the smallest value at the top
• the value of every node must be the smallest among the node values in its entire subtree or every node is smaller than its children