DSA 52: Array-Based Heaps - Exercises

1. Insert Value(11)

Into the heap below:

        10
    /       \
    9         8
  /  \       /   \
 6     5    7     4
/ \   /
2  1 3

1.1 Insert Value(11): Tony’s Solution

        10
    /       \
    9         8
  /  \       /   \
 6     5    7     4
/ \   / \
2  1 3  [11]

        10
    /       \
    9         8
  /  \       /   \
 6    [11]    7     4
/ \   / \
2  1 3   (5)

        10
    /       \
  [11]         8
  /  \       /   \
 6    (9)    7     4
/ \   / \
2  1 3   (5)

       [11]
    /       \
  (10)         8
  /  \       /   \
 6    (9)    7     4
/ \   / \
2  1 3   (5)

2. Delete Root(10)

from the heap below:

       {10}
    /       \
    9         8
  /  \       /   \
 6     5    7     4
/ \   /
2  1 3

2.1 Delete Root(10): Tony’ Solution

      {10}
    /     \
    9       8
  /  \     /   \
 6     5  7     4
/ \   /
2  1 (`3)

      [3]
    /     \
   (9)       8
  /  \     /   \
 6     5  7     4
/ \   /
2  1 ()

      (9)
    /     \
   [3]       8
  /  \     /   \
 6     5  7     4
/ \   /
2  1 ()

      (9)
    /     \
   (6)       8
  /  \     /   \
[3]    5  7     4
/ \   /
2  1 ()

or more accurately…

      (9)
    /     \
   (6)       8
  /  \     /   \
[3]    5  7     4
/ \   
2  1 

3. Pop() Heap & Insert() Array

A new heap is created inserting array from index 0 onwards [55, 22, 34, 10, 2, 99, 68], then the following happens:

• pop() operation from heap (one at a time) and
• insert() new array,

Question: What order are the values compared to original array?

4. Pop() Heap & Insert() Array: Tony’s Solution

Assuming max-heap as question does not specify.

4.1 Create max_heap via insert() from origin_array

original_array = [55, 22, 34, 10, 2, 99, 68]

4.1.1 insert(55, 22, 34, 10, 22)

insert(55, 22, 34, 10, 22) keeping the tree complete

        55  
    22      34
10      2   

Recall, a Complete Tree:

• is a tree that is:
• completely filled with nodes
• no nodes are missing.

4.1.2 insert(99)

        55  
    22       (34)  
10      2 [99]  

        55
    22       [99]  
10      2 (34)  

       [99]  
    22       (55)  
10      2 (34)  

4.1.3 insert(68)

        99  
    22       (55)  
10      2 34    [68]  

        99  
    22       [68]  
10      2 34    (55)

4.2 Create new_array via pop() of max_heap

        99  
    22      68
10      2 34   [55]

Psuedo-code delete_node:

1. pop() from root_node (e.g. 55)
2. replace last_node to root_node
3. trickle root_node to keep the tree complete

4.3 Expected Result: Descending Order of original_array

The question didn’t specifiy the working-out, thus by properties of max_heap or priority_queue, values removed or popped are:

• From Highest priority to lowest priority or value

Thus, new_array is expected to be the:

• original_array
• sorted in descending order

5. HeapSort()

Heapsort() is a sorting algorithm that:

• insert() all the values
• into a heap and then
• pop() each one.

The exact scenario in Question 4.

5.1 Heapsort() is \(O(NlogN)\)

Like Quicksort():

• insert() \(N\) values
• into the heap: each insertion takes \(log N\) steps.