堆排序松木

优先队列，优先级，处理动态的情况。例如：100万元素，选出前100名。（N个元素，前M个），时间复杂度NlogM。完全二叉树结构。

构建堆：

template<typename Item>class MaxHeap{private: Item *data; int count;public: MaxHeap(int capacity){ data = new Item[capacity+1]; //注意堆中[0]位置不放元素，从1开始存，所以数组大小要+1。 count = 0; } ~MaxHeap(){ delete[] data; } int size(){ return count; } bool isEmpty(){ return count == 0; }};

最大（最小）堆情况：

向上移动和插入节点：

 void shiftUp(int k){ while( k > 1 && data[k/2] < data[k] ){ swap( data[k/2], data[k] ); k /= 2; } } void insert(Item item){ assert( count + 1 <= capacity ); data[count+1] = item; count ++; shiftUp(count); }

向下移动和减少节点：

注意只能减少第一个节点，然后将最后一个节点放入第一个节点（为了保持完全二叉树），然后调整根节点和其他节点的位置。

 void shiftDown(int k){ while( 2*k <= count ){ int j = 2*k; // 在此轮循环中,data[k]和data[j]交换位置 if( j+1 <= count && data[j+1] > data[j] ) j ++; // data[j] 是 data[2*k]和data[2*k+1]中的最大值 if( data[k] >= data[j] ) break; swap( data[k] , data[j] ); k = j; } } Item extractMax(){ assert( count > 0 ); Item ret = data[1]; swap( data[1] , data[count] ); count --; shiftDown(1); return ret; }

简单堆排序：

（针对最大最小堆）每次取得都是顶端最值，所以只要不断取出即可排序。

 while( !maxheap.isEmpty() ) cout<<maxheap.extractMax()<<" "; cout<<endl;

堆排序：首先解决如何构建最大（最小）堆。

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();}

堆排序改进：

其实对于完全二叉树，只需要交换根节点和叶子节点即可，而最大的一个根节点是n/2，在构建最大（最小）堆的时候，只需要对根节点往下交换即可。

//构建堆 MaxHeap(Item arr[], int n){ data = new Item[n+1]; capacity = n; for( int i = 0 ; i < n ; i ++ ) data[i+1] = arr[i]; count = n; for( int i = count/2 ; i >= 1 ; i -- ) shiftDown(i); }//排序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();}

原地堆排序：

之前的排序都是先构造树，有没有可能原地排序（利用数组）？

思路：对数组第一位进行下移操作，然后和数组尾部进行交换。

需要注意：数组中从0开始计算，所以叶子节点为i*c+1和i*c+2，父节点为(i-1)/2。微修改下移函数。

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 heapSort(T arr[], int n){ for( int i = (n-1)/2 ; i >= 0 ; i -- ) __shiftDown(arr, n, i);//数组中先构建最大（小）树 for( int i = n-1; i > 0 ; i-- ){ swap( arr[0] , arr[i] ); __shiftDown(arr, i, 0); //对[0]节点进行处理即可。 }}