效果建网站的公,凡科网登陆,微信如何开通小程序,页游平台排行榜引言
什么是堆#xff1f;堆是一种特殊的数据结构#xff08;用数组表示的树#xff09;。
为什么要使用到堆#xff1f;比如一场比赛#xff0c;如果使用擂台赛的方式来决出冠军#xff08;实力第一#xff09;#xff0c;就很难知道实力第二的队伍是什么了。
但是…引言
什么是堆堆是一种特殊的数据结构用数组表示的树。
为什么要使用到堆比如一场比赛如果使用擂台赛的方式来决出冠军实力第一就很难知道实力第二的队伍是什么了。
但是下图能很清楚的表示各队伍的强弱关系。 堆的特点 上图就是一个最大堆解释每一个圆都是一个节点数字代表着键值其中95是93和92的父节点93和92是95的子节点93和92是兄弟节点父节点为同一个根节点就是键值最大的节点为95最后一个节点是87最后一个左子节点也是87。
最大堆的特点 满足以下三点 1.每个节点最多可以有两个子节点。 2.根节点的键值是所有堆节点键值中最大者且每个节点的值都大于其子孩子节点。 3.除了根节点没有兄弟节点最后一个左子节点可以没有兄弟节点其他节点必须有兄弟节点。 最好是自己理解不用强记 。其中有一点要注意A的兄弟节点的子节点可能大于A相当于在比赛中其中一个小组都是弱队那么一个弱队却可以闯入半决赛一样。
最小堆的特点的话就将第二点中的大改为小就可以了其他的特点一样。这里讨论的是最大堆
数组形式表示
父节点和子节点的关系 i 的左子节点2i1 右子节点2i2 i 的父节点i-1/2 i 是从 0 开始的 再将上图的堆转换为数组的形式如下图 这就是一个最大堆的数组表示形式。
在数组中快速创建堆
也就是怎么把任意一个数组变成最大/小堆。
我们先把堆的最小单位拿出来如下图 他不是一个最大堆如果要变成最大堆只需要父节点是95子节点分别是86、88就可以了86和95交换。而一个最大堆是由若干个这个最小单位组成的所以第一步就是将所有的堆的最小单位变成最大堆。 1、首先先找到最后一个节点的父节点找出该节点的最大子节点与自己比较如果大于自身就交换两个节点。 2、继续移动到上一个父节点也就是下标 -1 的地方重复做第一步的比较操作直到遍历所有的父节点。 当我们移动完所有的父节点那最大堆就形成了吗还疏忽了一个地方。例如当移动到某个父节点时如下图 最开始父节点是88与子节点95交换了那父节点就是9595 的子节点就是 88那88一定大于他的子节点吗很显然这个答案是不一定因为 88 的子节点只满足小于之前的父节点 95所以还需要向下调整直到子节点都小于父节点。 3、对每次移动中变成子节点的节点向下调整也就是判断他与子节点是否满足最大堆的特点不满足还要继续移动节点向下调整满足的话就接着下个父节点。 4、所有的节点交换完毕最大堆构建完成。 堆的算法实现
堆数据结构的定义
#define DEFAULT_CAPCITY 120 //默认的堆容量typedef struct _Heap
{int* arr; //存储堆元素的数组int size; //堆中元素的个数int capcity; //堆的容量
}Heap;//函数声明
void buildHeap(Heap heap);
bool inset(Heap heap, int value);
bool initHeap(Heap heap, int* orginal, int size);
void adjustDown(Heap heap, int i);
void adjustUp(Heap heap, int i);
堆的初始化
bool initHeap(Heap heap,int *orginal,int size)
{//orginal 是指向数组的指针而这个数组是我们要传入堆的数组int capcity DEFAULT_CAPCITY size ? DEFAULT_CAPCITY : size; //取size和默认容量的最大值heap.arr new int[capcity];if (!heap.arr) return false; //申请失败heap.capcity capcity;if (size 0) //size合法{memcpy(heap.arr, orginal, sizeof(int) * size);heap.size size;//建堆buildHeap(heap);}return true;
}
堆的创建
//建堆从最后一个父节点逐个向前调整所有的父节点直到根节点确保每一个父节点都是一个最大堆
//那么整体上就是一个最大堆
void buildHeap(Heap heap)
{int i (heap.size - 2) / 2; //因为下标从0开始heap.size-1就得到下标再结合公式就是这个式子for (; i 0; i--){adjustDown(heap, i); //向下调整包含了构建最大堆如果感到困惑先看向下调整函数}
}
堆的向下调整函数
void adjustDown(Heap heap, int i)
{int temp heap.arr[i]; //保存父节点的键值int parent 0 ,child 0;for (parent i; (2 * parent 1) heap.size; parent child) {child 2 * parent 1; //先指向左子节点//指向两个子节点中最大的节点if (child 1 heap.size heap.arr[child] heap.arr[child 1]){child child 1;}if (temp heap.arr[child]){break; //无需向下调整}else{heap.arr[parent] heap.arr[child];heap.arr[child] temp;}}
}
堆的插入新元素 1、插入新的元素到最大堆的尾部也就是数组的后面 2、插入的元素可能会破环这个最大堆需要重新调整和父节点比较如果比父节点大就交换两个节点……重复直到新节点比父节点小或者新节点变为根节点调整到位。 设计两个函数一个是插入一个是向上调整。 bool insert(Heap heap, int value)
{if (heap.size heap.capcity) //堆空间不足{return false;}int i heap.size ; //指向新加元素的下标heap.arr[heap.size] value;adjustUp(heap , i);return true;
}
void adjustUp(Heap heap, int i)
{if (i 0 || i heap.size) return;while (i 0){int parent (i - 1) / 2;if (parent 0) // 父节点没越界{if (heap.arr[parent] heap.arr[i]){int temp heap.arr[i];heap.arr[i] heap.arr[parent];heap.arr[parent] temp;i parent;}else{break; //无需调整}}else{break; //父节点出界}}
}
看到这你会发现堆的创建还有一种方式也就是将数组的元素一个一个插入也能得到最大堆。
源代码
#include iostreamusing namespace std;#define DEFAULT_CAPCITY 120 //默认的堆容量typedef struct _Heap
{int* arr; //存储堆元素的数组int size; //堆中元素的个数int capcity; //堆的容量
}Heap;void buildHeap(Heap heap);
bool insert(Heap heap, int value);
bool initHeap(Heap heap, int* orginal, int size);
void adjustDown(Heap heap, int i);
void adjustUp(Heap heap, int i);//初始化堆
bool initHeap(Heap heap,int *orginal,int size)
{//orginal 是指向数组的指针而这个数组是我们要传入堆的数据int capcity DEFAULT_CAPCITY size ? DEFAULT_CAPCITY : size; //取size和默认容量的最大值heap.arr new int[capcity];if (!heap.arr) return false;heap.capcity capcity;if (size 0){memcpy(heap.arr, orginal, sizeof(int) * size);heap.size size;//建堆buildHeap(heap);}return true;
}//建堆从最后一个父节点逐个向前调整所有的父节点直到根节点确保每一个父节点都是一个最大堆
//那么整体上就是一个最大堆
void buildHeap(Heap heap)
{int i (heap.size - 2) / 2; //因为下标从0开始heap.size-1就得到下标for (; i 0; i--){adjustDown(heap, i);}
}void adjustDown(Heap heap, int i)
{int temp heap.arr[i]; //父节点的键值int parent 0 ,child 0;for (parent i; (2 * parent 1) heap.size; parent child){child 2 * parent 1;//指向两个子节点中最大的节点if (child 1 heap.size heap.arr[child] heap.arr[child 1]){child child 1;}if (temp heap.arr[child]){break; //无需向下调整}else{heap.arr[parent] heap.arr[child];heap.arr[child] temp;}}
}//堆——插入新元素
bool insert(Heap heap, int value)
{if (heap.size heap.capcity){return false;}int i heap.size ;heap.arr[heap.size] value;adjustUp(heap , i);return true;
}void adjustUp(Heap heap, int i)
{if (i 0 || i heap.size) return;while (i 0){int parent (i - 1) / 2;if (parent 0) // 父节点没越界{if (heap.arr[parent] heap.arr[i]){int temp heap.arr[i];heap.arr[i] heap.arr[parent];heap.arr[parent] temp;i parent;}else{break; //无需调整}}else{break; //父节点出界}}
}
int main(void)
{Heap heap;int orginalArr[] { 1,2,3,87,93,82,92,86,95 };if (!initHeap(heap, orginalArr, sizeof(orginalArr) / sizeof(int))){cout 初始化堆失败 endl;exit(-1);}for (int i 0; i heap.size; i){printf(%d\n,heap.arr[i]);}puts();insert(heap, 100);for (int i 0; i heap.size; i){printf(%d\n, heap.arr[i]);}return 0;
}
