HGPA

Heaps

Introduction

Usually the word "heap" refers to an unordered pile of things, a mess. Many times it refers to a trash heap, a pile or fill of garbage.

In computer science, a heap usually refers to two different things:

The use of the word "heap" for these may not be a coincidence! Memory heaps hold dynamically (randomly) allocated memory with no particular order. Heap data structures do not maintain sequential order of their content. In other words, in some way, they are each a respective mess.

Furthering the analogy, some programming languages manage the automatic deallocation of memory within a heap with something called a garbage collector.

The heap data structure is useful for quickly getting the maximum or minimum element from a set. They are generally associated with priority queues, where the element with the highest priority is always at the front of the line.

You may have also heard of heapsort. This is a sorting algorithm that uses a heap to do all the work.

Heap Data Structures

heap-labeled tree:

Usually when we talk about heaps (data structure) we're referring to binary heaps. There are other types as well.

Introduction to Binary Heaps

I'm bigger and bolder and rougher and tougher. In other words sucker there is no other. I'm the one and only Dominator.

Say you have a list of numbers: 2 7 8 1 5 9 3.

We want to construct a data structure such that we can always get the dominating element in constant time. In the case of a min-heap it would be 1. This implies that all the real work needs to happen on element insertion and deletion.

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

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

Filename: heaps.md (Edit)
Modified: 2017-02-05 (1392974bb6ffb18bb5d06a8e7018d4b57ee24233)
Created: 2016-12-30 (20ec443fb31c0cabf78fce15350d4e166aa131f4)