深圳有什么网站,常熟沿江开发区人才网,百度seo外包,直播app下载汅api免费下载概念 性质: 1.堆是一颗完全二叉树#xff0c;用数组实现。 2.堆中存储数据的数据是局部有序的。 最大堆#xff1a;1.任意一个结点存储的值都大于或等于其任意一个子结点中存储的值。 2.根结点存储着该树所有结点中的最大值。 最小堆#xff1a;1.任意一个结… 概念 性质: 1.堆是一颗完全二叉树用数组实现。 2.堆中存储数据的数据是局部有序的。 最大堆1.任意一个结点存储的值都大于或等于其任意一个子结点中存储的值。 2.根结点存储着该树所有结点中的最大值。 最小堆1.任意一个结点存储的值都小于或等于其惹你一个子结点存储的值。 2.根结点存储着该树所有结点中的最小值。 无论最小堆还是最大堆任何一个结点与其兄弟结点之间都没有必然联系。 STL中并没有把heap作为一种容器组件heap的实现亦需要更低一层的容器组件诸如list,array,vector作为其底层机制。Heap是一个类属算法包含在algorithm头文件中。虽然STL中关于heap默认调整成的是大顶堆但却可以让用户利用自定义的compare_fuction函数实现大顶堆或小顶堆。heap的低层机制vector本身就是一个类模板heap基于vector便实现了对各种数据类型无论基本数据类型还是用户自定义的数据类型的堆排前提是用户自定义的数据类型要提供比较机制compare_fuction函数。 STL里面的堆操作一般用到的只有4个。 他们就是make_heap();、pop_heap();、push_heap();、sort_heap();他们的头函数是algorithm首先是make_heap();他的函数原型是void make_heap(first_pointer,end_pointer,compare_function);一个参数是数组或向量的头指针第二个向量是尾指针。第三个参数是比较函数的名字。在缺省的时候默认是大跟堆。下面的参数都一样就不解释了作用把这一段的数组或向量做成一个堆的结构。范围是(first,last)然后是pop_heap();它的函数原型是void pop_heap(first_pointer,end_pointer,compare_function);作用pop_heap()不是真的把最大最小的元素从堆中弹出来。而是重新排序堆。它把first和last交换然后将[first,last-1)的数据再做成一个堆。接着是push_heap()void pushheap(first_pointer,end_pointer,compare_function);作用push_heap()假设由[first,last-1)是一个有效的堆然后再把堆中的新元素加进来做成一个堆。最后是sort_heap()void sort_heap(first_pointer,end_pointer,compare_function);作用是sort_heap对[first,last)中的序列进行排序。它假设这个序列是有效堆。当然经过排序之后就不是一个有效堆了 #includealgorithm #includecstdio using namespace std; bool cmp(int a,int b) //比较函数 { return ab; } int main() { int i,number[20]{29,23,20,22,17,15,26,51,19,12,35,40}; make_heap(number[0],number[12]); //结果是:51 35 40 23 29 20 26 22 19 12 17 15 for(i0;i12;i) printf(%d ,number[i]); printf(\n); make_heap(number[0],number[12],cmp); //结果12 17 15 19 23 20 26 51 22 29 35 40 for(i0;i12;i) printf(%d ,number[i]); printf(\n); //加入元素8 number[12]8; //加入后调整 push_heap(number[0],number[13],cmp); //结果8 17 12 19 23 15 26 51 22 35 40 20 for(i0;i13;i) printf(%d ,number[i]); printf(\n); //弹出元素8 pop_heap(number[0],number[13],cmp); //结果12 17 15 19 23 20 26 51 22 29 35 40 for(i0;i13;i) printf(%d ,number[i]); printf(\n); sort_heap(number[0],number[12],cmp); //结果不用说都知道是有序的了 for(i0;i12;i) printf(%d ,number[i]); return 0; } 转载于:https://www.cnblogs.com/inception6-lxc/p/8483845.html
