//// Created by liuyubobobo on 8/15/16.//#ifndef INC_05_HEAPIFY_HEAP_H#define INC_05_HEAPIFY_HEAP_H#include <algorithm>#include <cassert>using namespace std;template<typename Item>class MaxHeap{private:    Item *data;    int count;    int capacity;    void shiftUp(int k){        while( k > 1 && data[k/2] < data[k] ){            swap( data[k/2], data[k] );            k /= 2;        }    }    void shiftDown(int k){        while( 2*k <= count ){            int j = 2*k;            if( j+1 <= count && data[j+1] > data[j] ) j ++;            if( data[k] >= data[j] ) break;            swap( data[k] , data[j] );            k = j;        }    }public:    MaxHeap(int capacity){        data = http://www.mamicode.com/new Item[capacity+1];>

template<typename T>void heapSort2(T arr[], int n){    MaxHeap<T> maxheap = MaxHeap<T>(arr,n);    for( int i = n-1 ; i >= 0 ; i-- )        arr[i] = maxheap.extractMax();}template<typename T>void heapSort1(T arr[], int n){    MaxHeap<T> maxheap = MaxHeap<T>(n);    for( int i = 0 ; i < n ; i ++ )        maxheap.insert(arr[i]);    for( int i = n-1 ; i >= 0 ; i-- )        arr[i] = maxheap.extractMax();}

template<typename T>void __shiftDown(T arr[], int n, int k){    while( 2*k+1 < n ){        int j = 2*k+1;        if( j+1 < n && arr[j+1] > arr[j] )            j += 1;        if( arr[k] >= arr[j] )break;        swap( arr[k] , arr[j] );        k = j;    }}template<typename T>void __shiftDown2(T arr[], int n, int k){    T e = arr[k];    while( 2*k+1 < n ){        int j = 2*k+1;        if( j+1 < n && arr[j+1] > arr[j] )            j += 1;        if( e >= arr[j] ) break;        arr[k] = arr[j];        k = j;    }    arr[k] = e;}template<typename T>void heapSort(T arr[], int n){    for( int i = (n-1)/2 ; i >= 0 ; i -- )        __shiftDown2(arr, n, i);    for( int i = n-1; i > 0 ; i-- ){        swap( arr[0] , arr[i] );        __shiftDown2(arr, i, 0);    }}