# CS2040 T04 Tutorial 5: Heaps and Priority Queues
> [name=jiachen]

## Recap

## Problem 1: True of False?

> For each of the following, determine if the statement is True or False, justifying your answer with appropriate explanation.

a. The smallest element in a min heap is always the root.

**TRUE**

b. The second largest element in a max heap with more than two elements (all elements are unique) is always one of the children of the root.

**TRUE**

c. When a heap is stored in an array, finding the parent of a node takes at least O(log n) time.

**FALSE**

d. Every node in the heap except the leaves has exactly 2 children

**FALSE**

e. We can obtain a sorted sequence of the heap elements in O(n) time.

**FALSE**

---

## Problem 2: Greater than x

Give an algorithm to find all vertices bigger than some value x in a max heap that runs in O(k) time where k is the number of vertices in the output.

#### Algorithm

def find_nodes_bigger(node, x):
    if node && node.key >= x:
        print(node.key)
        find_nodes_bigger(node.left, x)
        find_nodes_bigger(node.right, x)
        
# print out all nodes larger than in the tree
find_nodes_bigger(root, 10)

#### Analysis

**O(k + 2k)**,
- k nodes that have keys greater than x are guaranteed to be visited.
- For each of these k nodes there can be at most 2k additional calls to nodes with value smaller than x.

---

## Problem 3: Updating a heap
> Give an algorithm for the update(int old key, int new key) operation, which updates the value of old key in a binary heap (max or min) with new key in the binary heap in O(log n) time, which does not change the time complexity of the other operations.

> You are required to modify the other operations in the binary heap if needed, including any additional data structures used.

> You may assume all values in the heap will be unique.

The problem: It takes O(n) to traverse the array to look for the key to replace!

Solution: Maintain an additional hashtable to lookup keys to index. We can build this hashtable when `heapify` is called in O(n) time. `swap` in `shiftup` and `shiftdown` will now have to update the hashtable.

- update* in O(log n)
- lookup key index O(1)
- update new key O(1)
- call shift up O(log n)
- call shift down O(log n)
- insert in O(log n)
- extractMax in O(log n)
- heapify in O(n)
- build hash table

---

## Problem 4: Sorted? Almost.

k = 1
array = [1, 3, 2, 4, 5, 7, 6]

k = 2
array = [1, 4, 3, 2, 6, 5, 7]

|true position - actual position| <= k

### a) Give an algorithm to sort a partially sorted array in O(n) time, where k = 1.

- one pass bubble sort

### b) Give an algorithm to sort a partially sorted array in O(n log k) time, where k can be any positive integer smaller than n.

- k pass bubble sort? O(nk)
- ignore everything focus on the first element
- what are the possible positions for the first elem?
- sliding heap window

k = 4
[|5, 2, 3, 4, 1|, 6, 7, 8, 9]
[|5, 2, 3, 4, 1,| 6, 7, 8, 9]
[1,  |5, 2, 3, 4, 6|, 7, 8, 9]
[1, 2,  |5, 3, 4, 6|, 7, 8, 9]

#### Algorithm

def sort(arr, k):
    n = len(arr)
    
    # assume a new heap is provided
    h = heapify(arr[:k+1 # O(k)
    
    for i in range(n): # O(n)
        arr[i] = h.extractMin() # O(log k)
        
        if i + k + 1 < n:
            h.insert(arr[i + k + 1])# O(log k)

#### Analysis
O(k + n 2 log k)
= O(n log k)

---

## Problem 5

### Algorithm

k = 2, score = 4
[2, -10, 2, -6, 5]

k = 5, score = 9
[-1, -1, -1, -1, -1, 10]


### Analysis
Time: O(n log k)
Space: O(k)