HGPA

Binary Heaps

Read heaps first.

tl;dr

Implementations:

Introduction

A binary heap uses a complete binary tree.

Recall that complete binary trees:

Inserting into a binary heap:

  1. place new element in left most spot (n+1)
  2. "Bubble Up": if and while (new) element dominates parent
    • swap them

Swaps happen between levels, and a tree will have lg(n) levels. Since there are n items to be inserted, insertion will take O(nlogn).

Extracting the dominator from a binary heap:

  1. remove dominating element from top
  2. move last added element (bottom-right most leaf) into top
  3. "Bubble Down": if and while that element does not dominate its children:
    • swap it with lesser of two children

Implementing Binary Heaps

Since a binary heap is a complete binary tree we can implement it using an array.

Example: 2 7 8 1 5 9 3 pushed into min-heap as a tree:

    1
  2   3
 7 5 9 8

But as an array looks like: 1,2,3,7,5,9,8,. Notice this is equivalent to a breadth-first traversal.

This image from Wikipedia explains best: Implicit Binary Tree

So for some zero-based index i:

WARNING: Beware zero and one-based version of the above equations. Many references use one-based equations because the math/logic is cleaner, but programmers always use zero-based arrays.

Notice that floor(n/2) is the index of one or more the the middle items of the array:

To insert:

  1. append number to list
  2. "Bubble Up":

    • parent = heap[floor((i-1)/2)]
    • if parent < number then swap them
  3. Test your inserts

  4. Test your removals

Note:

Heap Interface:

We can store any binary tree in an array without pointers but:

RESOURCES

https://en.wikipedia.org/wiki/Binary_heap

8.4. heapq — Heap queue algorithm.

Filename: binary-heaps.md (Edit)
Modified: 2017-02-25 (2a439f02c6a8a5282b6b2152f312cbf219e25d4c)
Created: 2017-02-25 (2a439f02c6a8a5282b6b2152f312cbf219e25d4c)