Abdul Bari Algorithms - Heap, Heap Sort, Heapify, and Priority Queues
Describes the Heap data structure, the operations it supports, and its time complexity.
![](/_astro/heap_1673042424667_0.CE2uIKFy_Z26InKF.webp)
![](/_astro/heap_1673042424667_0.CE2uIKFy_17xk0k.webp)
Heap - Heap Sort - Heapify - Priority Queues
Array Representation of Binary Tree
[a,b,c,d,e,f,g]
{{youtube-timestamp 181}} You can store a binary tree as an array
When storing a binary tree we need store the elements as well as the relationship between the element
Binary Tree Representation Formula
##+BEGIN_NOTE He uses an array index starting at 1, but I converted it to an array with a 0 index ##+END_NOTE
if a node is at index i
the left child is at index 2*i+1
The right child is at index 2*i+2
The parent is at Math.floor((i-1)/2)
Examples
{{youtube-timestamp 245}} what is the left child of b
which is at index 1?
The left child index is 2*1+1
= 3, and the element at index 3 is d
{{youtube-timestamp 267}} What is the right child of b
which is at index 1?
The right child index is 2*1+2
= 4, and the element at index 4 is e
{{youtube-timestamp 296}} What is the parent of f
which is at index 5?
The parent child index is Math.floor((5-1)/2)
= 2, and the element at index 2 is c
You can also think about filling them level by level
Missing nodes at the end
[a,b,c,d,e]
leave out the missing elements at the end.
Gaps
{{youtube-timestamp 358}} Imagine filling it level by level, but leave a gap
[a,b,c,null,null,d,e]
children of b are missing, so leave a gap
Complete Binary Tree
Full Binary Tree
{{youtube-timestamp 450}} a Full binary tree has the maximum number of nodes for its height, you can’t add another node without increasing its height
{{youtube-timestamp 497}} The number of nodes in a full binary tree with height is
Complete Binary Tree
{{youtube-timestamp 512}} When represented as an array, a complete binary tree doesn’t have any gaps
Complete Binary Tree Example
Its array representation is [a,b,c,d,e,f,g]
and it has no gaps, so it’s a complete binary tree
Non complete binary tree
{{youtube-timestamp 532}} Its array representation is[a,b,c,null,null,d,e]
and has gaps, so it is not a complete binary tree.
Every full binary tree is also a complete binary tree
Heap
{{youtube-timestamp 876}} A heap is a complete binary tree
Max heap is a complete binary tree where every node is greater than or equal than its descendants. The largest node is the root
Min heap is a complete binary tree where every node is smaller than it’s descendants. The smallest node is the root.
Insert
{{youtube-timestamp 998}} We want to insert an element into a max heap
Array representation = [50,30,20,15,10,8,16]
Let’s try inserting 60
The root should have the largest element so the root should be 60
We need to maintain completeness while inserting
{{youtube-timestamp 1189}} We start by inserting 60
at the end of the array, which corresponds to the bottom left element of the complete binary tree. [50,30,20,15,10,8,16,60]
Swap upward with parents until the correct height
[60,50,20,30,10,8,16,15]
We add new element as leaf, then adjusts it’s ancestors upward
{{youtube-timestamp 1244}} How much time does it take? The maximum number of swaps, which is the height of a complete binary tree, which is
Delete
{{youtube-timestamp 1345}} You should only delete root element
Imagine picking an apple at the top of a pyramid at the supermarket
We delete 50
[50,30,20,15,10,8,16]
Remove 50, and replace with last element of the binary tree, 16
{{youtube-timestamp 1526}} Now we adjust the elements from the root towards leaf, maintaining complete binary property
Check 16’s child elements, which child is greater? 30
so swap with 30
Check 16’s child elements, which child is greater? 15
so swap with 15
Heap Sort
{{youtube-timestamp 1696}} If you keep deleting, the next largest element goes to the top in max heap. In min heap the next smallest comes to the top
After deleting the largest element, we have a “free space” at the end
Before deleting
[50,30,20,15,10,8,16]
After deleting
[30,10,20,15,10,8,null]
{{youtube-timestamp 1774}} We can keep the element we removed at at the end of the array to preserve it
[30,10,20,15,10,8,50]
Let’s delete again, removing 30
[20,16,10,15,8,null,50]
But we preserve 30 at the end of the heap
[20,16,10,15,8,30,50]
We can see that we’re sorting the array by deleting the largest element, and filling it in at the free space at the end of the new array
How to do heap sort
{{youtube-timestamp 1876}} Heap sort has two steps, create a heap from an array by inserting the elements one by one
Then delete the elements one by one
Heap Sort Example
Create Heap
{{youtube-timestamp 1913}} These are the unsorted set of elements [10,20,15,30,40]
Assume 10
is the root of the heap
Now insert second element 20
[10,20]
Compare with ancestor, 20 is greater, so swap
[20,10]
Now insert the third element 15
Compare with parent, it’s smaller, so we don’t need to adjust
[20,10,15]
Now insert the fourth element 30
[20,10,15,30]
Adjust the element by comparing to parent, greater than 10 so swap
Adjust the element by comparing to parent, greater than 20 so swap
Sorted, so now elements are [30,20,15,10]
Now insert the fifth element 40
[30,20,15,10,40]
Compare with parent and swap upward
Swap upward again
Now the heap is [40,20,15,10,20]
Every element was inserted at next free space and moved upward
We inserted n elements, each element was moved up the height of the binary tree
So we have elements moved up by height so time complexity to build heap is
Delete all elements
[40,20,15,10,20]
{{youtube-timestamp 2184}} 40 gets deleted and 20 takes it’s place at the root
[20,30,15,10]
Now we need to adjust the binary tree by swapping downward
{{youtube-timestamp 2229}} Check where of the children of 20 are greater, than swap
30
is greater, so swap 20
and 30
Compare 20
with 10
, don’t need to swap
[30,20,15,10]
[40]
, keeping 40
at the end
{{youtube-timestamp 2276}} 30
get’s deleted and the last element 10
takes its place at the root
[10,20,15]
Now adjust by comparing with children
Swap 10
, with 20
Now this is in map heap form, so we stop
20,10,15
and our reserved elements [30,40]
Now we delete 20
and replace with 15
We don’t need to adjust since the child is smaller
15,10
is the new heap and our reserved elements [20,30,40]
Now delete 15
and replace with 10
We don’t need to adjust since there’s just one element
Our heap is [10]
and our reserved elements at the end are [15,20,30,40]
So together now the array is sorted 10,15,20,30,40
Heapify
{{youtube-timestamp 2538}} Heapify is a procedure for creating a heap from a binary tree
Array representation [10,20,15,12,40,25,18]
{{youtube-timestamp 2549}} It’s similar to creating a heap from scratch. Before we saw when creating a heap from scratch, we insert from the root and adjust down. However, in heapify we adjust upwards.
We start with a complete binary tree, but it isn’t a max heap
{{youtube-timestamp 2595}} In heapify we go from right to left, instead of left to right in creating a heap
{{youtube-timestamp 2609}} When going from right to left, we adjust downward, similar to deletion
{{youtube-timestamp 2627}} Start with element 18
and look at it’s descendents. It’s a leaf with no children, so alone it is a heap. Continuing on we see the same with 25
, 40
, and 12
{{youtube-timestamp 2660}} We get to 15
and adjust downards. We compare it to it’s children and swap. Which child is greater? 25
is greater, so we swap with 15
. 25
goes up and 15
goes down, in its place
{{youtube-timestamp 2700}} Now we’re on 20
, Compare with children. 40
is greater, so swap 20
with 40
{{youtube-timestamp 2693}} Now we get to the first element, the root
{{youtube-timestamp 2709}} We compare 40 with it’s children, and swap 10 with 40
{{youtube-timestamp 2732}} We continue heapifying down, and check 10
’s children. 20
is greater so we swap with 10
{{youtube-timestamp 2777}} What is the time taken by heapify?
{{youtube-timestamp 2792}} The earlier procedure for creating a heap was , which is slower than heapify
Priority Queue
{{youtube-timestamp 2829}} Elements have priority, and inserted and deleted based on element
{{youtube-timestamp 2850}} Elements with the highest priority is removed
{{youtube-timestamp 2869}} In a numeric array, the priority is based on the number itself
{{youtube-timestamp 2904}} We can say that the highest priority is the smallest number, or we can say the largest number has the highest priority, depending on the use case. We can do either method of priority
{{youtube-timestamp 2966}} The time for insert or delete for a a regular array is because we have to shift the elements
{{youtube-timestamp 3007}} The time for insert or delete for a priority queue is which is faster than a normal array