Key Concepts

Review core concepts you need to learn to master this subject

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.

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.

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.

Chevron Left Icon
Heaps: Conceptual
Lesson 1 of 2
Chevron Right Icon
  1. 1
    Heaps are used to maintain a maximum or minimum value in a dataset. Our examples use numbers since this is a straight-forward value, but heaps have many practical applications. Imagine you have a…
  2. 2
    We can picture min-heaps as binary trees, where each node has at most two children. As we add elements to the heap, they’re added from left to right until we’ve filled the entire level. At th…
  3. 3
    Sometimes you will add an element to the heap that violates the heap’s essential properties. We’re adding 3 as a left child of 11, which violates the min-heap property that children must be larg…
  4. 4
    Maintaining a minimum value is no good if we can never retrieve it, so let’s explore how to remove the root node. In the diagram, you can see removing the top node itself would be messy: there wo…
  1. 1
    We’re going to implement a min-heap in Python. Min-heaps efficiently keep track of the minimum value in a dataset, even as we add and remove elements. Min-heaps are nearly identical to a max…
  2. 2
    Our MinHeap class will store two pieces of information: A Python list of the elements within the heap. A count of the elements within the heap. To make our lives easier, we’ll always keep on…
  3. 3
    The min-heap is no good if all it ever contains is None. Let’s build the functionality to add elements while maintaining the heap properties. Our MinHeap will abide by two principles: * The elem…
  4. 4
    Great work so far! Our MinHeap adds elements to the internal list, keeps a running count, and has the beginnings of .heapify_up(). Before we dive into the logic for .heapify_up(), let’s review how…
  5. 5
    Now that we understand how to determine the relationship of elements with the internal list, we’re ready to finish .heapify_up(). We need to make sure that every child is greater in value than th…
  6. 6
    Min-heaps would be useless if we couldn’t retrieve the minimum value. We’ve gone through a lot of work to maintain that value because we’re going to need it! Our goal is to efficiently remove
  7. 7
    We’ve retrieved the minimum element but left our MinHeap in disarray. There’s no reason to get discouraged, we’ve handled this type of problem before, and we can get our MinHeap back in shape! We…
  8. 8
    We mentioned .heapify_down() is a lot like .heapify_up(). We’ll track an offending element in the heap, and keep swapping it with another element until we’ve restored the heap properties. The wrin…
  9. 9
    We’ve got a handy helper to tell us which child element is smaller, so there’s nothing standing between us and a pristine heap. As a reminder, our strategy will be very similar to .heapify_up(), …
  10. 10
    Nice work! You’ve implemented a min-heap in Python, and that’s no small feat (although it could efficiently track the smallest feat). To recap: MinHeap tracks the minimum element as the element a…

How you'll master it

Stress-test your knowledge with quizzes that help commit syntax to memory

Pro Logo