CS61B Guide
  • This site is now deprecated
  • Object Oriented Programming
    • Inheritance
    • Access Control
    • Dynamic Method Selection
    • Java Objects
    • Generic Types
  • Asymptotics
    • Asymptotic Analysis Basics
    • Amortization
    • Asymptotics Practice
  • Abstract Data Types
    • Collections
      • Arrays
      • Linked Lists
      • Sets
      • Stacks and Queues
    • Binary Trees
      • Heaps
      • Balanced BSTs
      • Tries
    • Graphs
    • Hashing and Hash Tables
    • Union Find (Disjoint Sets)
    • Comparables and Comparators
  • Sorting
    • Sorting
  • Algorithms
    • Minimax Algorithm
    • Searching
      • Binary Search
      • Depth First Search (DFS)
      • Breadth First Search (BFS)
    • Shortest Paths
      • Dijkstra's Algorithm
      • A* Search
    • Minimum Spanning Trees
      • Prim's Algorithm
      • Kruskal's Algorithm
  • Misc Topics
    • Modular Arithmetic and Bit Manipulation
    • Exceptions
    • More Resources
Powered by GitBook
On this page
  • What are Heaps?
  • The Heapify Algorithm
  • Practical Applications

Was this helpful?

  1. Abstract Data Types
  2. Binary Trees

Heaps

PreviousBinary TreesNextBalanced BSTs

Last updated 5 years ago

Was this helpful?

What are Heaps?

A heap is a specific order of storing data, often in a list. Heaps are very similar to binary trees, but have some differences:

  • Unlike trees, heaps only care about the root node. Usually, the root node is either the largest or smallest value in the heap (corresponding with max-heaps and min-heaps), and we don't care too much about the rest.

  • Every element in the heap must be larger than all its children (in a max-heap) or smaller than all its children (in a min-heap). This is known as the heap property.

When stored in a list, there is an important rule to figure out how to identify parent nodes and their children: a node's parent has an index equal to half of that node's index. More specifically, parentIndex = nodeIndex / 2 where / has floor-division properties.

The Heapify Algorithm

The most important heap algorithm is heapify, which converts any non-heap list into a heap. This algorithm is vital to most heap functions like insert or remove, since these functions often break the heap structure before fixing it with heapify.

Start with the element in the middle of the array (which is the root of the heap).

If the root is smaller than either of its children (larger for a min-heap), swap it with its largest child (smallest for a max-heap).

If the root was swapped, recursively call heapify on the new position. Otherwise, stop recursion.

After heapify is complete, it should look like this:

Practical Applications

Here's how it works: (This example is an excerpt from my . The example provided is a max-heap [5,6,2,4,1].)

is a fantastic resource for practicing heap implementations and working with the algorithms that are needed to work with heaps (like heapify, insert, remove). Since this lab goes into plenty of detail about how each of these algorithms work, I won't explain them too much here.

Heap sort relies on the heap structure to provide consistent nlogn sorting! I have more information about this on page 11 in my .

Sorting Guide
Lab 9
sorting guide
Converting a heapified list into a min-heap diagram.