# [sorting] heap sort heap.img

## Pre-req.

### Binary tree:

• Every node at most has two kids.

### Full binary tree:

• Every level is full.
• K levels ⟺ 2^K-1 nodes.

### Complete binary tree:

• Except the last level, all levels are full.

• Because of the above properties, it can be represented by an array, where `left = root*2`, `right = root*2 +1`, and `root = kid // 2`.

• Becasue of array is usually zero- based, the below formulas are used in heap instead: `left = root*2 + 1`, `right = root*2 + 2`, and `root = (kid-1) // 2`

## Heap

* the codes below use min heap for default.

## Piority queue

A piority queue, where its element are tuples like (piority, item), is just a special heap. In python, because tuple comparision is available, heap is quivalent piority queue!

## Operations on Heap

### Heapify(array, i)

It adjust the tree under index i, making sure the ith element sinks down to its correct place.

or

### Build_heap(array)

This done by calling heapify(arr, i) from the bottom to the top, ensureing the array satisfies the heap property.

### Insert(array, ele)

This is done by adding the heap to the end, and sift it up to the correct position.

### Pop(array)

This is done by:

1. poping the root of the heap
2. fill the root with the last element in the array
3. heapify(arr, 0)

Notice keep popping will give a ordered array.

### Heapsort(array):

The complete sorting process includes

1. build the heap
2. ouput the min(max) of the heap one at a time to form a ordered array

## Performance

Each Heapify is log(n).

Building heap does n times of Heapify, hence nlog(n).

Each Pop calls Heapify once, hence log(n).

Totally there are n times of popping, hence nlog(n).

⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎

Worst = 2*nlog(n) = O(nlog(n))