Problems

Heapifying Array

Problem Statement:
Given an array, build a heap from it in O(n)

Approach:
If create an empty heap and insert each element into the heap, it takes O(n log n).

We can use the heap properties to solve it in O(n). The leaf nodes always satisfy the heap properties. So we only need to heapify the non-leaf nodes, which start at (n-1)/2.

fun buildHeap(val arr: List<Int>) {
    val heap = Heap()

    arr.forEach{ heap.add(it) } // not insert but add

    for(i in (arr.size-1)/2 downTo 0) {
        heap.heapify(i)
    }
}

---

Median in Infinite Series

Problem Statement: Median in an infinite series of numbers

Approach:
We solve this by using 2 heaps: a max-heap and a min-heap. Max-heap contains first half and min-heap will have the second half, when the elements are sorted. In case of odd number of elements min-heap will have one element more than max-heap.

class Stream {
    val minHeap = Heap()
    val maxHeap = Heap()
    var n = 0

    fun add(val data: Int) {
        // If n is even insert in maxHeap else in minHeap
        if (n % 2 == 0) {
            if(minHeap.peek() < data)
                maxHeap.insert(data)
            else{
                maxHeap.insert(minHeap.delete())
                minHeap.insert(data)
            }
        } else {
            if(maxHeap.peek() > data)
                minHeap.insert(data)
            else{
                minHeap.insert(maxHeap.delete())
                maxHeap.insert(data)
            }
        }
        n++
    }

    fun median(): Int {
        return if(n % 2 == 0) {
            (minHeap.peek() + maxHeap.peek()) / 2
        } else {
            minHeap.peek()
        }
    }
}

---

Merge 2 Heaps

Problem Statement: Given two heaps, how do you merge them?

Approach:
Binary heaps doesn't have an efficient way to merge two min-heaps into a single min-heap. For solving this efficiently, we can use mergeable heaps that support union operation.

Binomial Heap and Fibonacci Heap are two such heaps that support union operation efficiently.

---

Middle Priority

Problem Statement: Design a heap where an element with middle priority is returned first on peek and delete operations.

Approach:
Similar to the median problem, we can use two heaps.

---

Max Sliding Window

Problem Statement: Given an array and a sliding window size w. Return an array which contains maximum value of each window.

Approach:
We can use a max-heap and also keep track of the starting index of the current window. When ever the window moves we need to add the new element and remove top elements which are out of the window. Now the max element in the window will be the root of the heap.

Time Complexity of this approach is O(n log w)

It Can be solved in O(n) using double-ended queues LC 239.

---

Merge K sorted lists

Problem Statement: Given k sorted lists with total n elements. Give an algorithm to merge them.

Approach:
Build a max-heap with first elements from all k lists. Extract the max element and it to end the output. Then add a new element from the list where max is from to heap. Repeat

TC: O(n log k). SC: O(k)

---

Top k from a billion

Problem Statement: Given a file with a billion elements. Find the top k elements, where k is very small.

Approach:
Take the first 1000 elements and create a heap, which takes O(n). Find top k in the heap using heapsort logic. Get 1000 - k next elements + k elements from the previous set and create a new heap. Repeat until the ed of the file.

---

\(k^{th}\) largest

Problem Statement: Find the kth largest in the min-heap

Approach:
We can delete k times from the original heap, but this modifies the original heap.

If we should not modify the original heap. Create an auxiliary heap, add the root element into it and maintain a count. Delete the min from auxiliary heap and increase the count. If count is k return the value, else put the left and right child of the element into the auxiliary heap. Repeat until the count is k.

---