一、堆1. 概念与分类上一期我们提到二叉树的实现既可以用顺序结构也可以用链式结构。本篇我们来学习顺序结构的二叉树起个新名字——堆heap。堆是完全二叉树它的底层是顺序结构的数组具有二叉树特性的同时还有一些其他性质堆分为大堆和小堆或称为大根堆、小根堆大堆大堆的每个结点的存储值都 它的子结点的存储值。小堆小堆的每个结点的存储值都 它的子结点的存储值。譬如在一个大堆中某一个父结点的值为20则它的子结点的值一定20在一个小堆中某一个父结点的值为20则它的子结点的值一定20。左孩子和右孩子的值的大小关系不确定。换句话说一个堆一定是大堆或小堆。以下的二叉树既不是大堆也不是小堆它们就不是堆2. 结构与性质定义数据结构堆123456typedefstructHeap{HPDataType* arr;intsize;intcapacity;}HP;上面的画图是用逻辑结构表示堆用存储结构表示堆就要用到数组了牢记二叉树结点的编号方式从上到下从左到右不难推断堆的数组中有下列性质大堆的首元素根结点是整个堆的最大值小堆的首元素根结点是整个堆的最小值。若子结点的下标为i则它的父结点是(i-1)/2。若父结点的下标为i则它的左孩子是2i1右孩子是2i2。结点个数是n2i1 n 说明无左孩子2i2 n 说明无右孩子。顺带给出堆的初始化和销毁方法以及后面要用到的交换两个变量值的方法12345678910111213141516171819202122voidHPInit(HP* php){assert(php);php-arr NULL;php-size php-capacity 0;}voidHPDestory(HP* php){assert(php);if(php-arr ! NULL)free(php-arr);php-arr NULL;php-size php-capacity 0;}voidSwap(HPDataType* px, HPDataType* py){HPDataType tmp *px;*px *py;*py tmp;}3. 入堆想要把一个新的数据插入堆分为两步把它插入堆数组末尾仅仅插入数据后可能会破坏堆的性质所以还要进行“向上调整”操作将新插入结点顺着其双亲往上调整位置至满足大堆或小堆的位置。我们以下面一个小堆为例插入一个新数据10如果它小于其父结点不符合小堆两者交换。再和新父结点比较如果小于交换……直到满足小堆所以我们要知道向上调整算法它有两个参数要被调整的堆数组要调整位置的结点的下标12345678910111213141516171819voidAdjustUp(HPDataType* arr,intchild){intparent (child - 1) / 2;//找这个结点的父结点while(child 0){//调整的是小堆: //调整的是大堆: if(arr[child] arr[parent]){Swap(arr[child], arr[parent]);child parent;parent (child - 1) / 2;}else//新数据已经到了对的位置{break;}}}这样我们就能实现入堆操作了12345678910111213141516171819voidHPPush(HP* php, HPDataType x){assert(php);if(php-size php-capacity)//空间不够则需增容{intnewcapacity php-capacity 0 ? 5 : 2 * php-capacity;HPDataType* tmp (HPDataType*)realloc(php-arr, newcapacity *sizeof(HPDataType));if(tmp NULL){perror(relloc fail!);exit(1);}php-arr tmp;php-capacity newcapacity;}php-arr[php-size] x;//新数据插到末尾即下标为size的位置AdjustUp(php-arr, php-size);php-size;}测试我们来实现一个小堆乱序给一些数将打印结果排列成堆的逻辑结构看看发现确实是正确的小堆4. 出堆我们所谓的出堆出的并不是数组末尾数据出的是第一个数据——堆的根结点。但是直接除去数组首元素再将后面元素的下标全体前挪会使堆的所有结点位置关系“大乱套”再想调整可就麻烦了。因此我们选择这样的出堆定元素方法先将堆顶数据和堆的最后一个数据交换size- -把数组末尾数据出掉再对堆顶元素进行“向下调整”操作。相比刚才所有结点位置大乱套这样只要调整一个结点的位置就好了。向下调整算法和向上调整类似它是比较结点和其较大或较小孩子的值不断往下交换调整位置直至满足大堆或小堆向下调整算法有三个参数要被调整的堆数组、要调整的结点的下标、堆的数据个数1234567891011121314151617181920212223242526voidAdjustDown(HPDataType* arr,intparent,intn){intchild 2 * parent 1;while(child n){//调整的是小堆: //调整的是大堆: if(child 1 n arr[child] arr[child 1])//找两个孩子中的较大/较小者{child;}//调整的是小堆: //调整的是大堆: if(arr[child] arr[parent]){Swap(arr[child], arr[parent]);parent child;child 2 * parent 1;}else//调整完成{break;}}}这样我们就能实现出堆操作了12345678voidHPPop(HP* php){assert(php);assert(php-size ! 0);//堆不能为空否则无数据可出Swap(php-arr[0], php-arr[php-size - 1]);//交换堆顶和堆尾数据php-size--;//将堆尾数据出掉AdjustDown(php-arr, 0, php-size);}测试我们来实现一个大堆乱序给一些数再进行一次出堆分析逻辑结构可以看到大堆实现成功出堆也没有问题二、堆排序堆排序是一种排序方法不是借助堆的数据结构而是利用堆的思想进行排序一个n个元素的数组假如想排升序就将数组建成一个大堆堆顶是最大值将堆顶和堆尾交换下标n-1处就是最大值了我们再把前n-1个数据调整成大堆此时堆顶就是第二大的数据堆顶和堆尾交换下标n-2处就是第二大值了……直至排序完成。相反地想排成降序就建小堆道理是一样的我们下面就以建成大堆为例。
