淘客网站 源码,库存管理软件手机版,南昌地宝网出租房信息,物流网站建设可行性分析一、堆树的定义 堆树的定义如下#xff1a; #xff08;1#xff09;堆树是一颗完全二叉树#xff1b; #xff08;2#xff09;堆树中某个节点的值总是不大于或不小于其孩子节点的值#xff1b; #xff08;3#xff09;堆树中每个节点的子树都是堆树。 当父节点的键… 一、堆树的定义 堆树的定义如下 1堆树是一颗完全二叉树 2堆树中某个节点的值总是不大于或不小于其孩子节点的值 3堆树中每个节点的子树都是堆树。 当父节点的键值总是大于或等于任何一个子节点的键值时为最大堆。 当父节点的键值总是小于或等于任何一个子节点的键值时为最小堆。如下图所示左边为最大堆右边为最小堆。 二、堆树的操作 以最大堆为例进行讲解最小堆同理。 原始数据为a[] {4, 1, 3, 2, 16, 9, 10, 14, 8, 7}采用顺序存储方式对应的完全二叉树如下图所示 1构造最大堆 在构造堆的基本思想就是首先将每个叶子节点视为一个堆再将每个叶子节点与其父节点一起构造成一个包含更多节点的对。 所以在构造堆的时候首先需要找到最后一个节点的父节点从这个节点开始构造最大堆直到该节点前面所有分支节点都处理完毕这样最大堆就构造完毕了。 假设树的节点个数为n以1为下标开始编号直到n结束。对于节点i其父节点为i/2左孩子节点为i*2右孩子节点为i*21。最后一个节点的下标为n其父节点的下标为n/2。 如下图所示最后一个节点为7其父节点为16从16这个节点开始构造最大堆构造完毕之后转移到下一个父节点2直到所有父节点都构造完毕。 C代码实现 定义存放堆的结构如下 strcut MaxHeap{ Etype *heap; int HeapSize; int MaxSize;};MaxHeap H; 其中heap是数据元素存放的空间下标从1开始存数数据下标为0的作为工作空间存储临时数据。HeapSize是数据元素的个数MaxSize是存放数据元素空间的大小。 初始化堆方法如下 void MaxHeapInit (MaxHeap H){ for(int i H.HeapSize/2; i1; i--) { H.heap[0] H.heap[i]; int son i*2; while(son H.HeapSize) { if(son H.HeapSize H.heap[son] H.heap[son1]) son; if(H.heap[0] H.heap[son]) break; else { H.heap[son/2] H.heap[son]; son * 2; } } H.heap[son/2] H.heap[0]; }} 2最大堆中插入节点 最大堆的插入节点的思想就是先在堆的最后添加一个节点然后沿着堆树上升。跟最大堆的初始化过程大致相同。 C代码实现 void MaxHeapInsert (MaxHeap H, EType x){ if(H.HeapSize H.MaxSize) return false; int i H.HeapSize; while(i!1 xH.heap[i/2]) { H.heap[i] H.heap[i/2]; i i/2; } H.heap[i] x; return true;} 3最大堆中堆顶节点的删除 最大堆堆顶节点删除思想如下将堆树的最后的节点提到根结点然后删除最大值然后再把新的根节点放到合适的位置。 C代码实现 void MaxHeapDelete (MaxHeap H, EType x){ if(H.HeapSize 0) return false; x H.heap[1]; H.heap[0] H.heap[H.HeapSize--]; int i 1, son i*2; while(son H.HeapSize) { if(son H.HeapSize H.heap[0] H.heap[son1]) son; if(H.heap[0] H.heap[son]) break; H.heap[i] H.heap[son]; i son; son son*2; } H.heap[i] H.heap[0]; return true;} 三、堆树的应用 利用最大堆、最小堆进行排序。 堆排序算法详解http://blog.csdn.net/guoweimelon/article/details/50904231 参考文献 1、彻底弄懂最大堆的四种操作(图解程序)JAVA http://128kj.iteye.com/blog/1728555 2、最大堆、最小堆 http://blog.csdn.net/genios/article/details/8157031 转载于:https://www.cnblogs.com/leebxo/p/11058555.html
