Codecademy Logo

Heaps

Heap Implementation

Heaps are typically implemented with a data structure such as an array or Python list. These sequential structures allow access to elements in a particular order which is key to efficient use of heaps. Although binary trees are helpful for understanding the relationships between nodes of a heap, implementation using a tree is less efficient for storage and retrieval of elements.

A step-by-step min-heap implementation comparing a binary tree structure to an array/list structure. There is a grid with three rows and two columns labeled 'Min - Heap' at the top of the grid. On the left side of the grid there is a binary tree implementation of min-heap (each of the three rows in the left column are labeled 'Binary Tree'). On the right side of the grid there is an array (list) implementation of min-heap (each of the three rows on the right are labeled 'Array'). Both the binary tree and array implementations use the same values at the same indices. In the first row, first column for the binary tree implementation there is a binary tree with three nodes. Each of the nodes are a outlined in a white circle with a white number in the center of the circle. The nodes are connected to their parent/children node(s) with a straight line. The root node is 9, and to the left of the root node there is the text 'Index 0'. The left child node is 12 and has text to the left that says 'Index 1'. The right child node is 20, and there is text to the right that says 'Index 2'. This node (20) has a yellow circle outline, instead of white, to show that this is the current number being added to the heap. Each of the node labels are present in each row of the binary tree structure column. In the second column of the first row for the array implementation there are three squares from left to right that contain the numbers 9, 12, and 20. The first two squares, 9 and 12, are outlined in white, and the third, 20, is outlined in yellow. Again, to show that this is the current number being added to the heap. Under the line of squares there is a label 'Index:' followed by the numbers 0 (under the 9 square), 1 (under the 12 square), and 2 (under the 20 square). Like the binary tree structure column, these labels are present in each row of the array structure column. In the second row the number 14 is added to the heap. In the binary tree structure column 14 is added as a child node of 12, is labeled as 'Index 3' to the right of the number 14, and is contained in a yellow circle. In the array structure the number 14 is added to the end of the array at index 3, is labeled '3' under the newly added number, and is contained in a yellow box. In the third row the number 21 is added to the heap. In the binary tree implementation of min-heap the number 21 is added as the right child node of the number 12. The newly added number is contained in a yellow circle and has the label 'index 4' to the right of the number. In the array implementation of min-heap, the number 21 is added to the end of the array and is contained in a yellow box with the label '4' underneath the box.

Adding Elements: Heapify Up

When a new element is added to a heap, if heap properties are violated, the new child must swap with its parent until both child and root properties are restored. This process is called heapifying up, because of the upwards movement of the new element in this restorative process.

An example of the heapifying up process; adding an element to a heap. The initial heap: the root value is 2, its left child value is 5, and its right child value is 10. The value 5 has two children, its left child value is 11, and its right child value is 14. On the right side of the heap, the value 10 has two children, its left child value is 20, its right child value 12. We want to add 3 to the heap which starts as the left-most child value, as a child of the value 11. First we compare 11 to 3. Since 3, the child value, is less than the parent value, 11, we will swap the values and make 11 a child value of 3. Next, we compare 3 to its new parent value, 5. Because the child value is less than its parent we swap the 3 and 5. Finally, we compare 3 to its new parent value, 2, which is the root. Because 3 is greater than 2 we do not need to swap the values. Our final heap is as follows: The root is 2. 2 has two children, the left child is 3, the right is 10. 3 has two children, the left is 5 and the right is 14. 5 has one child, 11. The right side of the heap remains the same.

Heaps as Binary Trees

A proper representation of a heap is a complete binary tree, which is a tree whose nodes have at most two children, and whose levels are filled completely from left to right (with no gaps in children). It’s possible for the last level to be semi-completely filled, but all of its nodes are as far left as possible.

Implementing the Heap Class

The basis of a Heap class in Python is the implementation of a heap with a list, based on the parent-child relationships that a binary tree structure portrays. The class also consists of multiple methods that provide the functionality to construct these parent-child relationships in the list, add elements, remove the root element, and heapify in both directions when necessary.

class MinHeap:
  "Some key methods to be included in the MinHeap class"
  
  def __init__(self):
    "Creates a list and count variable"
    self.heap_list = [None]
    self.count = 0
    
  def retrieve_min(self):
    "Replaces root with last child, calls .heapify-down()"
    
  def add(self, element):
    "Adds new element to heap_list, calls heapify_up()"
    
  def get_smaller_child_idx(self, idx):
    "Returns the child a parent should swap with"
    
  def heapify_up(self): 
    "Implements heapify up"
    
  def heapify_down(self):
    "Implements heapify down"
Previous

Learn More on Codecademy

Skill path

Pass the Technical Interview with Python

Learn about the computer science concepts of data structures and algorithms and build implementations of each from scratch in modern Python.
Includes 8 Courses
With Certificate
Intermediate
25 hours