CS 70

Binary Heaps

  • LHS Cow speaking

    The most common encoding of a priority queue is structure called a binary heap.

  • RHS Cow speaking

    It's a tree structure that organizes data in a different way than BSTs.

A binary min-heap is a binary tree such that

  1. Structure Property: The tree is complete.
    • Every level except (possibly) the last is full.
    • The last level is filled in from left to right.
  2. Order Property: There are two kinds of heaps: min-heaps (which have the smallest element at the top) and max-heaps (which have the largest).
    • In a min-heap, the key in every node is at least as small as all of its children.
    • In a max-heap, the key in every node is at least as big as all of its children.
  • LHS Cow speaking

    We'll focus on min-heaps in our discussions.

  • Duck speaking

    Is each subtree also a heap?

  • LHS Cow speaking

    Yes, that's implied by our rules above!

The picture below shows a heap—in this case, it only shows the keys (we can just assume that every node contains an associated value as well).

Notice that left and right are not relevant to how the data is organized, just above and below.

  • Dog speaking

    Does this heap anything to do with the heap we use for new and delete? Is that this kind of heap?

  • LHS Cow speaking

    No. “The Heap” is a region of program memory, and has no relationship to the binary-heap data structure.

  • Goat speaking

    Meh. It's like names were in short supply or something.

Representing a Heap

Although we visualize a heap as a binary tree, in practice we don't usually encode it using nodes and pointers.

Instead, the structure property of a heap allows us to represent it using an array!

  • Horse speaking

    Hay! How do you represent a tree with an array?

  • LHS Cow speaking

    Well, this isn't just any tree. It's a complete tree.

  • RHS Cow speaking

    Since it has no gaps, a level-order traversal tells us everything we need to know!

We would typically encode the binary heap shown above as the level-order traversal of its elements.

A level-order traversal lists all the nodes in each layer from top to bottom, going left to right within each layer.

This arrangement as an array has a very cool property that you can work out what the index of a child node is given the index of its parent. See if you can figure it out. If we have a node at index i, what is the index of its left child as a formula in terms of i?

(You can look at the diagram above to help try to work it out from some concrete examples.)

And where is the right child compared to the left child?

In general, the node at index \( i \) has its

  • Left cildren at index \( 2i + 1 \)
  • Right child at index \( 2i + 2 \)
  • Parent at index \( \lfloor (i - 1) / 2 \rfloor \) (where \( \lfloor x \rfloor \) is the floor function, which rounds down to the nearest integer).
  • Dog speaking

    Woah! This array-based encoding has a lot less space overhead than having all those pointers to nodes and so on.

  • LHS Cow speaking

    It will also have some runtime efficiency benefits, as we will see!

Getting the Minimum Element

In a binary min-heap, what is the complexity of the GET-MIN operation?

Because of the heap property that the key in a node is always the smallest in its subtree, we know that the minimum key must be in the root!

The root of the tree is stored at index 0 in the array, so we can access it in \( \Theta(1) \) time.

  • Duck speaking

    That's so simple! Always access index 0!

  • LHS Cow speaking

    Easy access to the minimum element is the whole point of a binary heap!

  • RHS Cow speaking

    Now the trick is to maintain these properties as items are inserted/removed.

(When logged in, completion status appears here.)