一.Min_heap的建立
堆是一种数据结构,分为最大值堆和最小值堆;
堆的内部结构是一个完全二叉树;
最大值堆的根节点是树中最大的元素,而父节点比任意一个子节点都要大;
最小值堆的根节点是树中最小的元素,父节点比任意一个子节点都要小;
我们用以下数组为建堆的材料:int testH[]={24,63,23,47,232,46,12,57,24,74};
逻辑中,我们对数组的结构可以这样设计:
-----图有点错了,最后两个是8和9
我们要建立一个堆,最重要的是三点:初始化堆,堆内调整算法,插入/删除;
设节点的下标为i(i!=0),孩子为2*i,2*i+1.
如果heap[i]>min(heap[2*i],heap[2*i+1])则交换节点,然后调整比如heap[2*i]与其孩子heap[2*2*i],heap[2*2*i+1].
节点规则:heap[i]<heap[2*i],heap[i]<heap[2*i+1];
(1)初始化堆我们的思想是从一个最小单元开始排序,就是最后一个父节点开始向前排序,而父节点的父节点是重叠子问题,只要最后一个父节点是最优的结构,往上解最优的时候就会获得全局最优的解集。
(2)当我们调整一个节点的时候,我们只需要往那个交换的节点的子节点进行调整。最小堆的一个规则,最简单的结构到复杂的结构的特点都是唯一的,也就是父节点比任意一个子节点都小。例如:
我们要调整55这个节点,44,和46已经调整好了(从后往前调整),55>46>44,则交换55和44这两个节点。这是不必调整46和它的子节点,理由很简单,它是个稳定的结构,没有进行节点调整,所以程序不必理会,而交换的44节点的结构变换了,要向下调整。所以建堆的思路是:从父节点往前调整,每一次调整深度优先。
初始化算法:
//初始化 void inith(int *a) { for(int i=0;i<hlength;i++) { heap[i]=*(a+i); } cout<<endl; } //建立堆 void build() { for(int i=hlength/2;i>=0;i--) { down(i); } } //从上往下调整法 void down(int p) { int q=p*2; int a=heap[p]; while(q<hlength) { if(q<hlength && heap[q]>heap[q+1]) { q++; } if(heap[q]>=a) { break; } else{ heap[p]=heap[q]; p=q; q=p*2; } heap[p]=a; } }
代码虽然很简单,但是思路确实很烦躁,要理解每一步的关键
最后形成的堆是:
-------更新 2014-11-15 22:00
实现最小堆的目的:堆排序
堆排序可以对大量的数据进行查找top k 而不占用大量的内存,原因是不用把数据加载到内存中,读入-堆比较-调整堆,这个流程,只要维护一个最小堆,top k不在话下
思路:利用最小值堆找出海量数据的前 k个最大值,比堆顶小的数据舍弃,比堆顶大的数据则替换掉堆顶并且向下调整,最后找出top k
#include <iostream> #include "heap_sort_min.h" using namespace std; void main() { int test[]={34,22,145,23,2,35,155,3245,1341,345,889,536,567,3546,786,468,468,464,48,646}; //int testH[]={24,63,23,47,232,46,12,57,24,74}; inith(test); build(); for(int i=9;i<20;i++) HeapSort(test[i]); for(int i=0;i<10;i++) cout<<heap[i]<<" "; cout<<endl; }
/*堆排序模块*/ void HeapSort(int a) { if(a<heap[0]) return; heap[0]=a; down(0); }
二.指针queue
类似Java的数组队列,而我所称的数组队列并不是严格的FIFO规则,只是一个可增长的动态数组,而指针的细节在于替代了原始地址要释放空间,不然会造成内存泄露
/* 数组队列 */ int *array; int size=10; int capacity=0; void queue() { array=new int[10]; } void add(int data) { int *temp; int *at=array; if(capacity==size) { temp=new int[++size]; for(int i=0;i<capacity;i++) temp[i]=array[i]; temp[size-1]=data; array=temp; delete[] at; capacity++; }else{ array[capacity++]=data; } }
最后一句:人生在于不停地奋斗,没有妹子就要孤独地写代码
<!--EndFragment-->
相关推荐
使用方法如下: ...python native_heapdump_viewer.py --symbols symbols 00.txt >00.log python native_heapdump_viewer.py --symbols symbols 01.txt >01.log 对比00.log和01.log,查看内存增长的点
min_MAX Heap!! Algorithm
最近在学习STL的源代码,看到这么多优秀的代码,心里痒痒的,于是自己实现了一遍,当然,有自己的特色,都是模块函数,稍稍用了一些traits特性。相互学习,呵呵
用VC++实现test_heap_sort算法,程序可读性高,比较不错。
在keil中的高阶应用,使用$$等特殊符号实现高阶功能。 区域ZI部分固定了起始和结束,所以计算时是可预知的。结束未预知的情况
java[1].lang.OutOfMemoryError_Java_heap_space错误及处理办法java[1].lang.OutOfMemoryError_Java_heap_space错误及处理办法java[1].lang.OutOfMemoryError_Java_heap_space错误及处理办法
解决Java_heap_space问题
ion heap ion heap create for Linux v2.13.6.
mozilla_nntp_heap_overflow
Heap Datastructure made by C++
(实际起限制作用的是tmp_table_size和max_heap_table_size的最小值。)如果内存临时表超出了限制,MySQL就会自动地把它转化为基于磁盘的MyISAM表,存储在指定的tmpdir目录下,默认: mysql> show variables like ...
可以用在OD里面看堆,插件的用法自行百度
drivers staging android ion ion_chunk_heap.
Linux_Heap_Internals.pdf
binary_heap_for_A_star
Unity Heap Profiler
Java Heap Solved Samples