「算法」堆和堆排序

堆排序松木

优先队列，优先级，处理动态的情况。例如：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;
 }
};

欢迎大家来到IT世界,在知识的湖畔探索吧!

最大（最小）堆情况：

向上移动和插入节点：

欢迎大家来到IT世界,在知识的湖畔探索吧! 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;
 }

简单堆排序：

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

欢迎大家来到IT世界,在知识的湖畔探索吧! 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]节点进行处理即可。
 }
}