Entrepreneurials‎ > ‎Jobs‎ > ‎Interview‎ > ‎Examples‎ > ‎

## Heap Sort

### Heap

The (binary) heap data structure is an array object that we can view as a nearly complete binary tree.

although A[1 .. A: length] may contain numbers, only the elements in A[1..A:heap-size], where 0 <= A:heap-size <= A:length, are valid elements of the heap.

 PARENT(i)1 return [i/2]LEFT(i)1 return 2*iRIGHT(i)1 return 2*i + 1 max-heap: A[PARENT(i)]  >= A[i]

height is Θ(lg n)

```MAX-HEAPIFY(A,i)     //heapify a specific node (move it down tree if necessary)
1 l = LEFT(i)
2 r = RIGHT(i)
3 if l <= heap-size[A] and A[l] > A[i]
4    then largest = l
5    else largest = i
6 if r <= heap-size[A] and A[r] > A[largest]
7    then largest = r
8 if largest != i
9    then exchange A[i] <-> A[largest]
10         MAX-HEAPIFY(A,largest)```
The size of a subtree is at most 2n/3, which occurs when the last row is exactly half full. So the worst case running time T(n) satisfies the recurrence:   T(n) <= T(2n/3) + Θ(1)     Which by case 2 of the "Master Theorem" has the solution: T(n) = O(lg n).
because a = 1 then nlogba becomes O(1), therefore ti is equal to f(n), hence  O(1* lg n)

```BUILD-MAX-HEAP(A)
1 A.heap-size = A.length
2 for i = floor(A.length/2) downto 1    //the entries in A[floor(n/2)+1..n] are all leaves
3     MAX-HEAPIFY(A,i)
```

Heap-Sort:   Build maxheap O(lg n) + traverse (n lg n) => O(n lg n)