# Heap

TODO

- Complete sorting section of notes
- Complete random alogorithms section of notes before stack
- Search all uses cases of min/max heap
- python heapq, use as min/max heap

This playlist has heap in the opposite order

- In my notes and Python, top of the heap is 0th index element
- In the playlist, top of the heap is the last element in the array
- This causes the switch in min/max heap

## Identification

These two must be given

- "K"
- "smallest" or "largest"

Also, the heap questions are mostly focused on sorting. The question can be solved using sorting in $O(nlogn)$. But with heap we can reduce the complexity to O(nlogk).

- K + smallest -> max_heap
- K + largest -> min_heap

This is because, when you want to get the K smallest elements, you push the other elements (that are larger than K) to the top of the heap and remove them. This way your heap has size K.

Problem - kth smallest element arr = [7, 10, 4, 3, 20, 15] k = 3

Make max heap of size k = 3

- Top element is max of arr of size 3
- [7, _, _]
- [7, 10, _]
- [4, 7, 10]
- [3, 4, 7]
- [3, 4, 7]
- [3, 4, 7]
- Here top of the heap is the rightmost element

## kth smallest element

- make max-heap and return top in the end

## return k largest elements in arr

- make min-heap and return the heap in the end

## sort a k sorted array (or a nearly sorted array)

k-sorted means, a value at index x, can be present in any index [x - k, x + k] in the sorted array.

make a min-heap of size k + 1, and that should be sufficient.

whenever the heap overflows, that element can be placed in the sorted array.

For arr = [6, 5, 3, 2, 8, 10, 9] and k = 3

- [_, _, _, _]
- [6, _, _, _]
- [6, 5, _, _]
- [6, 5, 3, _]
- Now the next 2 would be at the top, so put it in the output array and repeat

## k closest numbers

arr = 5, 6, 7, 8, 9 k = 3 x = 7 Fund 3 numbers from the array that are closes to 7

subtract 7 from all elements in the array, and then find the 3 minimum numbers (use max-heap)

for negative numbers you would have to take the absolute difference. And then store a pair in the heap this time `<orig_number, x - orig_number>`

.

## top k frequent numbers

- Use hasmap to get element, frequency pair
- Then use heap to get the greatest k elements

## frequency sort

- the least frequent elements should come first and so on
- Similar to previous problem, but use the heap on frequency and put those number of elements in the output array.

## connect ropes to minimise the cost

arr = [1, 2, 3, 4, 5] elements of arr give length of each rope

we want to connect these ropes, and minimize the cost of that. If 4,5 are connected then new rope length = 9, so cost is 9.

Keep connecting the minimum pairs, till only 1 is left.

## sum of elements between k1 smallest and k2 smallest numbers

- just find the k1, k2 elements
- traverse the array and get the sum