# Binray Heap

## Properties:
1. must be complemet binary tree: assume node at index i, then the index for parent node is arr[(i-1) / 2], left child is arr[2i + 1], right child is arr[2i + 2]  
2. the key of any node is no smaller than the key of its children(max heap)  


## build heap
Heapify procedure can be applied to a node only if its children nodes are heapified. So the heapification must be performed in the bottom up order.

## running time
To analyze the running time, consider what happens when we’re looking at a node x that’s
in level h (where we say that the bottom level is level 0, so the level is the height). We might have to sink x all the way to the bottom, which takes time h. But there are at most ceil(n/2^(h+1)) nodes at level h. So the total cost is only
\begin{equation}
\sum_{h=0}^{log\,n} h\cdot n/2^{h+1} \,\,\leq\,\, \sum_{h=0}^{log\,n} n\cdot h/2^{h+1} \,\,\leq\,\, O(n)
\end{equation}


```python
arr = [12, 3, 45, 66, 7, 8, 9, 11, 13]
def heapify(arr, n, i):
    largest = i
    l = 2 * i + 1
    r = 2 * i + 2
    if l < n and arr[largest] < arr[l]:
        largest = l
    if r < n and arr[largest] < arr[r]:
        largest = r
    if largest != i:
        arr[largest], arr[i] = arr[i], arr[largest]
        heapify(arr, n, largest)
        
def build(arr):
    n = len(arr)
    for i in range(n, -1, -1):
        heapify(arr, n, i)

build(arr)
arr
```




    [66, 13, 45, 12, 7, 8, 9, 11, 3]



## heap sort
After building a max heap, extract the elements one by one.
## running time
Time complexity for heapify is O(logn), since there are n loops, the total running time is O(nlogn)


```python
def heap_sort(arr):
    n = len(arr)
    for i in range(n - 1, -1, -1): 
        arr[i], arr[0] = arr[0], arr[i] 
        heapify(arr, i, 0)
heap_sort(arr)
arr
```




    [3, 7, 8, 9, 11, 12, 13, 45, 66]



## deletion, insertion, decrease key is similar to the operations shown above
for deletion, we can swap x with the last node, remove x, and then
restore heap order by sinking down. This takes O(log n) time.  

for insertion, we begin by inserting x into the next open spot, then we have it swim up until we restore the heap order. This takes O(log n) time.  

for decrease key, we can just decrease the key of x, and have it swim up until we
restore heap order. This takes O(log n) time.


```python

```

2677524e56d53ac13258e34d04c9fb49910a061f
ipynb
Jupyter Notebook
working related/binary_heap.ipynb
xinyaoliu/xinyaoliu.github.io
e8ea104231ff8be55ca577b00d1e73fbb7ef0c66
MIT
2019-02-05T22:58:30.000Z
2019-02-05T23:10:08.000Z
working related/binary_heap.ipynb
xinyaoliu/xinyaoliu.github.io
e8ea104231ff8be55ca577b00d1e73fbb7ef0c66
MIT
working related/binary_heap.ipynb
xinyaoliu/xinyaoliu.github.io
e8ea104231ff8be55ca577b00d1e73fbb7ef0c66
MIT
2019-02-05T22:58:18.000Z
2019-02-05T22:58:18.000Z
Qwen/Qwen-72B
1. YES
2. YES