[C++]数据结构之堆-上滤下滤以及用于排序

#include<iostream>
using namespace std ;
 
/*
* 堆，就是一棵完全二叉树，物理存储方式是数组，一般情况下，都牺牲第一个元素arr[0]，剩下的就满足了从1开始计数
* 若堆从1开始计数，那么对于一个节点i，2*i是它的左孩子，2*i+1是它的右孩子
* 对的最基本操作，包括上滤和下滤
* 上滤是指：h(1,n-1)是堆，h(1,n)不是堆，因此通过将arr[n]元素上滤，来达到调整堆的目的
* 下滤是指：h(2,n)是堆，h(1,n)不是堆，因此通过将arr[1]元素下滤，来达到调整堆的目的
*/
 
#define HEAP_SIZE 10 //这里，我要要建一个堆，堆里面要放10个元素
#define ARR_SIZE (HEAP_SIZE+1) //之前说过，堆默认的实现是牺牲掉第0个元素
#define HeapElemType int //定义堆的元素类型
 
//HeapElemType  HeapArray[ARR_SIZE];//堆的存储空间
 
/*
* 大顶堆，上面的，是最大的
* 堆的基本操作：上滤
* h(1,n-1)是堆，h(1,n)非堆，也就是说，只要调整第n个元素，就是一个新堆了
* 注意：n是当前可用元素的最大下标，它是不能超过ARR_SIZE的
*/
void shiftUp ( HeapElemType   HeapArray [ ] , int n ) {
     HeapElemType tmp = HeapArray [ n ] ;
     while ( n / 2 >= 1 && tmp > HeapArray [ n / 2 ] ) {
         HeapArray [ n ] = HeapArray [ n / 2 ] ;
         n = n / 2 ;
     }
     HeapArray [ n ] = tmp ;
}
 
/*
* 大顶堆，上面的，是最大的
* 堆的基本操作：下滤
* h(2,n)是堆，h(1,n)不是堆，也就是所，只要调整第1个元素，就是一个新的大顶堆
* 注意：n是当前堆中元素的最大下表，是不能超过ARR_SIZE的
*/
void shiftDown ( HeapElemType   HeapArray [ ] , int first , int n ) {
     HeapElemType tmp = HeapArray [ first ] ;
     int father = first , child ;
     while ( ( child = 2 * father ) <= n ) {
         //获取孩子中较大的孩子下标
         if ( child + 1 <= n && HeapArray [ child ] < HeapArray [ child + 1 ] ) child ++ ;
         //比较源节点和较大孩子，看是否需要继续调整
         if ( tmp > HeapArray [ child ] ) break ;
         //否则的话，孩子往上走
         HeapArray [ father ] = HeapArray [ child ] ;
         father = child ;
     }
     HeapArray [ father ] = tmp ;
}
void printHeapArr ( const HeapElemType   HeapArray [ ] , const int n ) {
     for ( int i = 1 ; i <= n ; ++ i ) {
         cout << HeapArray [ i ] << " " ;
     }
     cout << endl ;
}
void swap ( HeapElemType   HeapArray [ ] , int i , int j ) {
     HeapElemType tmp =      HeapArray [ i ] ;
     HeapArray [ i ] = HeapArray [ j ] ;
     HeapArray [ j ] = tmp ;
}
/*
* 堆排序：用堆的属性，即大顶堆最顶部的就是最大的节点
* 因此我们可以每次将根节点和末尾节点交换，然后将除了末尾节点的其他节点重新调整一个堆，然后循环
* 在做上一步之前，需要将杂乱的节点调整成一个堆
*/
void heapsort ( HeapElemType   HeapArray [ ] , int n ) {
     //第一步，先将杂乱的数组调整成一个大顶堆，需要n/2次调整就可以
     int tmp = 0 ;
     for ( tmp = n / 2 ; tmp >= 1 ; tmp -- ) {
         shiftDown ( HeapArray , tmp , n ) ;
     }
     //第二步，交换第一个节点（最大值）和末尾节点，然后调整除了末尾节点的其他节点为一个新大顶堆
     for ( tmp = n ; tmp > 1 ; tmp -- ) {
         swap ( HeapArray , 1 , tmp ) ;
         shiftDown ( HeapArray , 1 , tmp - 1 ) ;
     }
}
void main ( ) {
     cout << "上滤" << endl ;
     HeapElemType   HeapArray [ ARR_SIZE ] = { 0 , 5 , 4 , 2 , 3 , 6 } ;
     int n = 5 ;
     printHeapArr ( HeapArray , n ) ;
     shiftUp ( HeapArray , n ) ;
     printHeapArr ( HeapArray , n ) ;
 
     cout << "下滤" << endl ;
     HeapElemType   HeapArraySec [ ARR_SIZE ] = { 0 , 1 , 5 , 2 , 3 , 4 } ;
     n = 5 ;
     printHeapArr ( HeapArraySec , n ) ;
     shiftDown ( HeapArraySec , 1 , n ) ;
     printHeapArr ( HeapArraySec , n ) ;
 
     cout << "排序" << endl ;
     HeapElemType   HeapArraySort [ ARR_SIZE ] = { 0 , 1 , 4 , 2 , 3 , 5 , 6 } ;
     n = 6 ;
     printHeapArr ( HeapArraySort , n ) ;
     heapsort ( HeapArraySort , n ) ;
     printHeapArr ( HeapArraySort , n ) ;
 
     system ( "pause" ) ;
}