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.

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.

Previous

Learn More on Codecademy

Career path

Full-Stack Engineer

A full-stack engineer can get a project done from start to finish, back-end to front-end.
Includes 51 Courses
With Professional Certification
Beginner Friendly
169 Lessons
Career path

Back-End Engineer

Back-end developers deal with the hidden processes that run behind the scenes, building APIs and databases that power the front-end.
Includes 41 Courses
With Professional Certification
Beginner Friendly
122 Lessons
Career path

Front-End Engineer

Front-end engineers work closely with designers to make websites beautiful, functional, and fast.
Includes 34 Courses
With Professional Certification
Beginner Friendly
131 Lessons