### Heap
- Binary heap is complete binary tree (stored as an array)
- Complete binary tree are all levels of a binary tree are completly filled except last level

- This property helps to store the items as an array
- Item Access
- Advantages
- Random access due to contiguous memory location
- Cache friendly
- height is controlled which optimizes all operations
- storage space is compact
### Types
- Two Types
- Min Heap
- Highest piority item assigned lowest value
- Max Heap
- Highest piority item assigned higest value

- Min Heap
- complete binary tree
- every node has the value smaller than its decentents
- means zeroth node the the smallest
### Applications
- Used in Heap Sort
- Used in Priority Queue
- Useful in many standard algorithms such as
- Dijtras Shortest path algorithm
- Prims min spanning tree algorithm
- Huffmen endcoding

### Python Implimentation

from heapq import heappush, heappop, heapify

h = []

heapify(h)

heappush(h, (5, 'write code'))
heappush(h, (7, 'release product')
heappush(h, (1, 'write spec'))
heappush(h, (3, 'create tests'))
heappop(h)

heappushpop()  # push an item and pop an item perfrom better than push and pop seperately 
heapreplace() # pop and push an item

### Operations
- heapify - O(n)
- heappush - O(logn)
- heappop - O(logn)
- h[0] -> O(1) - check top item

### Construction
- Implement min heap
- insert
- insert item at the end of the array (becomes complete binary tree)
- compare newly inserted node with parent if leaf is smaller then swap and repeat
- TC O(logn) SC: O(1)
- heapify and extract
- min heapify: given a binary heap with one possible voilation, fix the heap
- assume root voilates the min heap property
- compare with children and swap the min with root
- and do the same recursively
- Extract min - swap root element with last elment and call heapify on the root
- decrease key
- apply the chnage
- compare with parent and swap if current elemtn is smaller than the parent and repeat recursicely
- delete
- decrease key to -inf then it will move to root
- execute extract min
- build heap
- call minheapify (which heify the childrens) for all internal parents from end
- start from ((n - 1) - 1)/ 2 till zero
- TC: O(n)
- Heapsort
- Piority Queue

### Problems
- heap sort
- min_heap, max_heap
- k largest element
- use minheap of size k
- algorithm
- for every element check
- add to heap if current element is equals or greater than first element
- return the first element
- TC: O(nlogk)
- SC: O(k)
- k smallest element
- use maxheap of size k
- algorithm
- for every element check
- add to heap if current element is equals or smaller than first element
- return the first element
- TC: O(nlogk)
- SC: O(k)
- find median
- init max_heap and min_heap
- for each element
- check if element is less than first element of max_heap if yes add to max_heap or add to min_heap
- balance the size between both heap if size difference is more than one
- if min max heap size are same
- take top item and return the everage
- if max_heap size is more then return top value
- if min_heap size is more then return top value
- find median of a stream
- similar to finding median
- sort k sorted array
- element at index i will be present between indexes i - k and i + k in sorted array
- merge k sorted array
- add first elements from k arrays in to minheap. item (item, ki, kj)
- until heap is empty
- pop one item and add next item in that array to heap
- top k frequent items
- find frequency of each item using dict or counter
- using min heap find the k frequent items
- buy maximum items with given sum
- sort items
- keep getting the items until given sum is reached
- TC: O(nlogn)
- k closest elements
- find k closest elements to x
- init max heap
- get min elements of abs(arr[i] - x)
- TC: O(nlogk)
- minimum cost of ropes
- rearrange charecters
- hiffman encoding
- binary heap operations
- maximize the array

### References