• ref. [Horowitz 7.7] [Neapolitan 7.6]

• Name	1	2	3	4	5	6	7	8	9	10
  unordered	26	5	77	1	61	11	26	15	48	19
  max heap	77	61	59	48	19	11	26	15	1	5
  ordered	1	5	11	115	19	26	48	59	61	77

• Method

  1. Convert an input array of n unordered items into a max heap.
  2. Extract the items from the heap one at a time to build an ordered array.

• 주어진 정수들을 비감소 순서(non-decreasing order)대로 정렬하라.

typedef struct{
  int key;
 /* other fields */
} element;
Element list[MAX_SIZE];

void heapsort(element list[], int n){ 
    /*perform heapsort on the array*/
    int i, j;
    element temp; 
    
    // (1) Make a (max) heap  
    for(i = (n)/2; i > 0; i--)     
        adjust(list, i, n);  

    // (2) Extract items one by one 
    for(i = n - 1; i > 0; i--) {
        SWAP(list[1], list[i+1], temp);
        adjust(list, 1, i);  
    }
}
        

1. O(n)
2. O(n\log n) \rightarrow O(n\log n)

• Make a (max) heap.

  Name	1	2	3	4	5	6	7	8	9	10
  unordered	26	5	77	1	61	11	26	15	48	19
  max heap	77	61	59	48	19	11	26	15	1	5
  ordered	1	5	11	115	19	26	48	59	61	77

• 

• Input: a binary tree T whose left and right subtrees satisfy the heap property but whose root may not

• Output: a binary tree T adjusted so that the entire binary tree satisfies the heap property

  void adjust(element list[], int root, int n){
      int child, rootkey;
      element temp;
      temp = list[root];
      rootkey = list[root].key;
      child = 2 * root;
      while (child <= n){
          if ((child < n) && (list[child].key < list[child + 1].key))
              child++;
          if (rootkey >= list[child].key)
              break;
          else{
              list[child / 2] = list[child];
              child *= 2;
          }
      }list[child / 2] = temp;
  }

• Executed d times, where d is the depth of the tree with root i

  • So O(d) time

• C_{MH} \leq (k-1)2^0 + (k-2)2^1 + (k-3)2^2 + ...+1 \cdot 2^{k-2}

• I= (k-1)2^0 + (k-2)2^1 + (k-3)2^2 + ...+1 \cdot 2^{k-2}

• 2I= (k-1)2^1 + (k-2)2^2 + (k-3)2^3 + ...+1 \cdot 2^{k-1}

• 2I-1I= -(k-1) + 2^1+ 2^2 + ... + 2^{k-2}

• I = -k+ \frac {1 \cdot (2^k-1)}{2-1} = 2^k -k -1

  \therefore C_{MH} \leq 2^k -k -1

• Time Complexity Analysis

  • 2^k \leq 2n, -k < -log_2 n
  • then 2^k -k -1 < 2n - log_2n -1
  • so C_{MH} = O(n)

for(int i=n/2; i>0;i--) adjust(list,i,n);
for(int i=n-1;i>0;i--){
  SWAP(list[1], list[i+1], temp);
  adjust(list,1,i);
}

2^c \leq n < 2^{c+1} \rightarrow c \leq \log_2 n < c+1

• for a given n, the cost (depth) is c = ⌊\log_2n⌋

• C_{IE}=⌊\log (n-1)⌋+⌊\log (n-2)⌋+⌊\log (n-3)⌋...+⌊\log2⌋+⌊\log 1⌋ \leq \log2 + \log3 + ...+\log {(n-1)} < \sum_{i=2}^n \log_2 n= O(n \log n)

• Heap Sort : C_{MH} +C_{IE} = O(n)+ O(n \log n) = O(n \log n)