Abdul Bari Algorithms - Heap, Heap Sort, Heapify, and Priority Queues

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 $h$ is $2^{h+1}-1$

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 $O(log(n))$

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 $n$ elements moved up by height $log(n)$ so time complexity to build heap is $n\ast log(n)$

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? $O(n)$

{{youtube-timestamp 2792}} The earlier procedure for creating a heap was $O(n\ast log(n))$, 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 $O(n)$ because we have to shift the elements

{{youtube-timestamp 3007}} The time for insert or delete for a priority queue is $O(log(n))$ which is faster than a normal array