精华内容
下载资源
问答
  • heap

    2015-11-23 15:33:15
    //最大堆 #ifndef HEAP_H_ #define HEAP_H_ #include using namespace std; class Heap { private: vector heapData; int heapSize; //堆中元素的个数 public: Heap(int *arr,int n);


    //最大堆
    #ifndef HEAP_H_
    #define HEAP_H_
    
    #include <vector>
    using namespace std;
    class Heap
    {
    private:
    	vector<int> heapData;
    
    	int heapSize;                               //堆中元素的个数
    public:
    	Heap(int *arr,int n);                       //构造函数,n为数组元素个数
    	void percolateUp(int index, int value);      //从index(下标)上溯
    	void adjustHeap(int holeIndex, int value);        //调整以holeIndex为根的子树为堆
    	void pushHeap(int addValue);
    	void popHeap(int choose=0);                 //默认不删除,choose=1时,表示删除该元素,释放内存
    	void makeHeap();
    	void display();
    	void sort();                //排序
    };
    
    
    //构造函数
    Heap::Heap(int *arr,int n)
    {
    	heapSize = n;
    	for (int i = 0; i < n; i++) heapData.push_back(arr[i]);
    	makeHeap();
    }
    
    //上溯
    void Heap::percolateUp(int index, int value)
    {
    	int holeIndex = index;
    	int parent = (holeIndex - 1) / 2;
    	while (holeIndex >0 && heapData[parent]<value)    //**错过
    	{
    		heapData[holeIndex] = heapData[parent];
    		holeIndex = parent;
    		parent = (holeIndex - 1) / 2;
    	}
    	heapData[holeIndex] = value;
    }
    
    //调整以holeIndex为根的子树为堆,对应值为value,从上往下
    void Heap::adjustHeap(int holeIndex, int value)
    {
    	int topIndex = holeIndex;
    	int rightChild = topIndex * 2 + 2;
    	while (rightChild < heapSize)
    	{
    		if (heapData[rightChild - 1] > heapData[rightChild]) rightChild--;
    		heapData[holeIndex]=heapData[rightChild];
    		holeIndex = rightChild;
    		rightChild = 2 * rightChild + 2;          //找到新的洞节点的右孩子
    	}
    	if (rightChild == heapSize)
    	{
    		heapData[holeIndex] = heapData[rightChild - 1];
    		holeIndex = rightChild - 1;
    	}
    	heapData[holeIndex] = value;        //**错过,STL源码剖析里面没有这个
    	percolateUp(holeIndex,value);   //上溯调节
    }
    
    //往堆中加入一个元素
    void Heap::pushHeap(int addValue)
    {
    	heapData.push_back(addValue);
    	++heapSize;
    	adjustHeap(heapSize - 1, heapData[heapSize - 1]);
    }
    
    //往堆中取出一个元素
    void Heap::popHeap(int choose)
    {
    	int adjustValue = heapData[heapSize-1];
    	heapData[heapSize - 1] = heapData[0];     //将第一个放到堆尾;
    	--heapSize;
    	if (choose==1) heapData.pop_back();
    	adjustHeap(0, adjustValue);             //**错过,是从上往下
    }
    
    //生成堆
    void Heap::makeHeap()
    {
    	if (heapSize < 2) return;
    	int holeIndex = (heapSize - 2) / 2;  //最后一个节点的parent
    	while (1)
    	{
    		adjustHeap(holeIndex, heapData[holeIndex]);
    		if (holeIndex == 0) return;
    		--holeIndex;
    	}
    }
    
    //显示堆
    void Heap::display()
    {
    	for (int i = 0; i < heapSize; i++)
    		cout << heapData[i] << " ";
    	cout << endl;
    }
    
    //排序
    void Heap::sort()
    {
    	int temp = heapSize;
    	while (heapSize > 0)
    		popHeap();
    	heapSize = temp;
    }
    #endif

    #include <iostream>
    #include "Heap.h"
    
    using namespace std;
    
    
    int main()
    {
    	int a[9] = {0,1,2,3,4,8,9,3,5};
    	Heap heap1(a, 9);
    	//heap1.pushHeap(7);
    	//heap1.display();
    	//heap1.popHeap();
    	heap1.sort();
    	heap1.display();
    	return 0;
    }


    展开全文
  • Heap

    2012-05-26 09:08:21
    Heap 译为"堆"是Java虚拟机JVM的内存数据区。Heap 的管理很复杂,每次分配不定长的内存空间,专门用来保存对象的实例。在Heap 中分配一定的内存来保存对象实例,实际上也只是保存对象实例的属性值,属性的类型和对象...
    Heap 译为"堆"是Java虚拟机JVM的内存数据区。Heap 的管理很复杂,每次分配不定长的内存空间,专门用来保存对象的实例。在Heap 中分配一定的内存来保存对象实例,实际上也只是保存对象实例的属性值,属性的类型和对象本身的类型标记等,并不保存对象的方法(方法是指令,保存在Stack中),在Heap 中分配一定的内存保存对象实例和对象的序列化比较类似。而对象实例在Heap 中分配好以后,需要在Stack中保存一个4字节的Heap 内存地址,用来定位该对象实例在Heap
     中的位置,便于找到该对象实例。 
    
      由于Stack的内存管理是顺序分配的,而且定长,不存在内存回收问题;而Heap 则是随机分配内存,不定长度,存在内存分配和回收的问题;
    展开全文
  • 文章目录前言Heap-buffer-overflowHeap-use-after-freeStack-buffer-overflowGlobal-buffer-overflow 前言 在做LeetCode题时发现一个有趣的事情。 对于C语言来说,如果直接访问超出Index的数组,会报错: int main...

    前言

    在做LeetCode题时发现一个有趣的事情。
    对于C语言来说,如果直接访问超出Index的数组,会报错:

    int main(int argc, char **argv) {
        int array  [100];
        array[101] = -1;
        int res = array[-1];  
        return res;
    }
    

    报错如下:

    Runtime Error:
    Line 3: Char 10: runtime error: index 101 out of bounds for type 'int [100]' (solution.c)
    

    但是如果你使用malloc分配空间给int数组,index的越界访问是不会直接报错的

    Heap-buffer-overflow

    但是LeetCode 使用了AddressSanitizer检查是否存在内存非法访问

    #include <stdlib.h>
    int main(int argc, char **argv) {
        int *array = (int*)malloc(100 * sizeof(int));
        array[0] = -1;
        int res = array[-1];  // BOOM
        return res;
    }
    

    LeetCode 报错如下:

    =================================================================
    ==30==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x60300000000c at pc 0x000000401749 bp 0x7ffc91bd0570 sp 0x7ffc91bd0568
    WRITE of size 4 at 0x60300000000c thread T0
        #3 0x7ff2c35d42e0 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x202e0)
    
    0x60300000000c is located 4 bytes to the left of 20-byte region [0x603000000010,0x603000000024)
    allocated by thread T0 here:
        #0 0x7ff2c4a5e2b0 in malloc (/usr/local/lib64/libasan.so.5+0xe82b0)
        #4 0x7ff2c35d42e0 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x202e0)
    
    Shadow bytes around the buggy address:
      0x0c067fff7fb0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
      0x0c067fff7fc0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
      0x0c067fff7fd0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
      0x0c067fff7fe0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
      0x0c067fff7ff0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
    =>0x0c067fff8000: fa[fa]00 00 04 fa fa fa fa fa fa fa fa fa fa fa
      0x0c067fff8010: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
      0x0c067fff8020: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
      0x0c067fff8030: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
      0x0c067fff8040: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
      0x0c067fff8050: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
    Shadow byte legend (one shadow byte represents 8 application bytes):
      Addressable:           00
      Partially addressable: 01 02 03 04 05 06 07 
      Heap left redzone:       fa
      Freed heap region:       fd
      Stack left redzone:      f1
      Stack mid redzone:       f2
      Stack right redzone:     f3
      Stack after return:      f5
      Stack use after scope:   f8
      Global redzone:          f9
      Global init order:       f6
      Poisoned by user:        f7
      Container overflow:      fc
      Array cookie:            ac
      Intra object redzone:    bb
      ASan internal:           fe
      Left alloca redzone:     ca
      Right alloca redzone:    cb
    ==30==ABORTING
    

    其实这是AddressSanitizer 这个工具的内存损坏检查报的错。
    可以在Linux上运行如下命令,检查程序是否存在内存非法访问:

    gcc -O -g -fsanitize=address  test.c
    ./a.out
    

    Linux下运行报错如下:

    allocated by thread T0 here:
        #0 0x7f8eb21bfd28 in malloc (/usr/lib/x86_64-linux-gnu/libasan.so.3+0xc1d28)
        #1 0x563aa79a68bd in main /root/test4.c:3
    
    SUMMARY: AddressSanitizer: heap-buffer-overflow /root/test4.c:5 in main
    Shadow bytes around the buggy address:
      0x0c287fff9f70: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
      0x0c287fff9f80: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
      0x0c287fff9f90: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
      0x0c287fff9fa0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
      0x0c287fff9fb0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
    =>0x0c287fff9fc0: fa fa fa fa fa fa fa[fa]00 00 00 00 00 00 00 00
      0x0c287fff9fd0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
      0x0c287fff9fe0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
      0x0c287fff9ff0: 00 00 00 00 00 00 00 00 00 00 fa fa fa fa fa fa
      0x0c287fffa000: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
      0x0c287fffa010: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
    Shadow byte legend (one shadow byte represents 8 application bytes):
      Addressable:           00
      Partially addressable: 01 02 03 04 05 06 07 
      Heap left redzone:       fa
      Heap right redzone:      fb
      Freed heap region:       fd
      Stack left redzone:      f1
      Stack mid redzone:       f2
      Stack right redzone:     f3
      Stack partial redzone:   f4
      Stack after return:      f5
      Stack use after scope:   f8
      Global redzone:          f9
      Global init order:       f6
      Poisoned by user:        f7
      Container overflow:      fc
      Array cookie:            ac
      Intra object redzone:    bb
      ASan internal:           fe
      Left alloca redzone:     ca
      Right alloca redzone:    cb
    ==7489==ABORTING
    
    

    Heap-use-after-free

    同时,AddressSanitizer也可以检查Heap-use-after-free的错:

    int main(int argc, char **argv) {
      int *array = new int[100];
      delete [] array;
      return array[argc];  // BOOM
    }
    
    g++ -O -g -fsanitize=address heap-use-after-free.c
    ./a.out
    

    报错如下:

    =================================================================
    ==7849==ERROR: AddressSanitizer: heap-use-after-free on address 0x61400000fe44 at pc 0x56282de47977 bp 0x7fff9cfc65e0 sp 0x7fff9cfc65d8
    READ of size 4 at 0x61400000fe44 thread T0
        #0 0x56282de47976 in main /root/heap-use-after-free.c:4
        #1 0x7fabfddb72e0 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x202e0)
        #2 0x56282de47819 in _start (/root/a.out+0x819)
    
    0x61400000fe44 is located 4 bytes inside of 400-byte region [0x61400000fe40,0x61400000ffd0)
    freed by thread T0 here:
        #0 0x7fabfea96370 in operator delete[](void*) (/usr/lib/x86_64-linux-gnu/libasan.so.3+0xc3370)
        #1 0x56282de47941 in main /root/heap-use-after-free.c:3
    
    previously allocated by thread T0 here:
        #0 0x7fabfea95d70 in operator new[](unsigned long) (/usr/lib/x86_64-linux-gnu/libasan.so.3+0xc2d70)
        #1 0x56282de47931 in main /root/heap-use-after-free.c:2
    
    SUMMARY: AddressSanitizer: heap-use-after-free /root/heap-use-after-free.c:4 in main
    Shadow bytes around the buggy address:
      0x0c287fff9f70: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
      0x0c287fff9f80: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
      0x0c287fff9f90: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
      0x0c287fff9fa0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
      0x0c287fff9fb0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
    =>0x0c287fff9fc0: fa fa fa fa fa fa fa fa[fd]fd fd fd fd fd fd fd
      0x0c287fff9fd0: fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd
      0x0c287fff9fe0: fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd
      0x0c287fff9ff0: fd fd fd fd fd fd fd fd fd fd fa fa fa fa fa fa
      0x0c287fffa000: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
      0x0c287fffa010: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
    Shadow byte legend (one shadow byte represents 8 application bytes):
      Addressable:           00
      Partially addressable: 01 02 03 04 05 06 07 
      Heap left redzone:       fa
      Heap right redzone:      fb
      Freed heap region:       fd
      Stack left redzone:      f1
      Stack mid redzone:       f2
      Stack right redzone:     f3
      Stack partial redzone:   f4
      Stack after return:      f5
      Stack use after scope:   f8
      Global redzone:          f9
      Global init order:       f6
      Poisoned by user:        f7
      Container overflow:      fc
      Array cookie:            ac
      Intra object redzone:    bb
      ASan internal:           fe
      Left alloca redzone:     ca
      Right alloca redzone:    cb
    ==7849==ABORTING
    

    Stack-buffer-overflow

    int main(int argc, char **argv) {
      int stack_array[100];
      stack_array[1] = 0;
      return stack_array[argc + 100];  // BOOM
    }
    
    gcc -O -g -fsanitize=address  test.c
    ./a.out
    

    报错如下:

    =================================================================
    ==8078==ERROR: AddressSanitizer: stack-buffer-overflow on address 0x7fffe55a7b04 at pc 0x555dec997a0e bp 0x7fffe55a7940 sp 0x7fffe55a7938
    READ of size 4 at 0x7fffe55a7b04 thread T0
        #0 0x555dec997a0d in main /root/test6.c:4
        #1 0x7f903bdab2e0 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x202e0)
        #2 0x555dec997819 in _start (/root/a.out+0x819)
    
    Address 0x7fffe55a7b04 is located in stack of thread T0 at offset 436 in frame
        #0 0x555dec99792f in main /root/test6.c:1
    
      This frame has 1 object(s):
        [32, 432) 'stack_array' <== Memory access at offset 436 overflows this variable
    HINT: this may be a false positive if your program uses some custom stack unwind mechanism or swapcontext
          (longjmp and C++ exceptions *are* supported)
    SUMMARY: AddressSanitizer: stack-buffer-overflow /root/test6.c:4 in main
    Shadow bytes around the buggy address:
      0x10007caacf10: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
      0x10007caacf20: 00 00 00 00 00 00 00 00 00 00 f1 f1 f1 f1 00 00
      0x10007caacf30: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
      0x10007caacf40: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
      0x10007caacf50: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
    =>0x10007caacf60:[f4]f4 f3 f3 f3 f3 00 00 00 00 00 00 00 00 00 00
      0x10007caacf70: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
      0x10007caacf80: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
      0x10007caacf90: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
      0x10007caacfa0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
      0x10007caacfb0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
    Shadow byte legend (one shadow byte represents 8 application bytes):
      Addressable:           00
      Partially addressable: 01 02 03 04 05 06 07 
      Heap left redzone:       fa
      Heap right redzone:      fb
      Freed heap region:       fd
      Stack left redzone:      f1
      Stack mid redzone:       f2
      Stack right redzone:     f3
      Stack partial redzone:   f4
      Stack after return:      f5
      Stack use after scope:   f8
      Global redzone:          f9
      Global init order:       f6
      Poisoned by user:        f7
      Container overflow:      fc
      Array cookie:            ac
      Intra object redzone:    bb
      ASan internal:           fe
      Left alloca redzone:     ca
      Right alloca redzone:    cb
    ==8078==ABORTING
    
    

    Global-buffer-overflow

    int global_array[100] = {-1};
    int main(int argc, char **argv) {
      return global_array[argc + 100];  // BOOM
    }
    
    gcc -O -g -fsanitize=address  test.c
    ./a.out
    

    报错如下:

    SUMMARY: AddressSanitizer: global-buffer-overflow /root/test6.c:3 in main
    Shadow bytes around the buggy address:
      0x0ab033158fe0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
      0x0ab033158ff0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
      0x0ab033159000: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
      0x0ab033159010: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
      0x0ab033159020: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
    =>0x0ab033159030: 00 00 00 00 00 00 00 00 00 00 00 00 00 00[f9]f9
      0x0ab033159040: f9 f9 f9 f9 00 00 00 00 00 00 00 00 00 00 00 00
      0x0ab033159050: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
      0x0ab033159060: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
      0x0ab033159070: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
      0x0ab033159080: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
    Shadow byte legend (one shadow byte represents 8 application bytes):
      Addressable:           00
      Partially addressable: 01 02 03 04 05 06 07 
      Heap left redzone:       fa
      Heap right redzone:      fb
      Freed heap region:       fd
      Stack left redzone:      f1
      Stack mid redzone:       f2
      Stack right redzone:     f3
      Stack partial redzone:   f4
      Stack after return:      f5
      Stack use after scope:   f8
      Global redzone:          f9
      Global init order:       f6
      Poisoned by user:        f7
      Container overflow:      fc
      Array cookie:            ac
      Intra object redzone:    bb
      ASan internal:           fe
      Left alloca redzone:     ca
      Right alloca redzone:    cb
    ==8158==ABORTING
    
    展开全文
  • STL heap

    千次阅读 2020-08-19 11:31:42
    Heap分为max heap和min heap,max heap中每次取出的结点时heap结构中值最大的结点,min heap中每次取出的结点时heap结构中值最小的结点。 Heap不允许遍历其结点,所以Heap没有迭代器。 在实际应用中,经常用vector...

    Heap堆是常用的数据结构,Heap中也可以存放元素。但是STL中并没有提供Heap容器,只是提供了关于Heap操作的算法。只要支持RandomAccessIterator的容器都可以作为Heap容器。

    Heap分为max heap和min heap,max heap中每次取出的结点时heap结构中值最大的结点,min heap中每次取出的结点时heap结构中值最小的结点。

    Heap不允许遍历其结点,所以Heap没有迭代器。

    在实际应用中,经常用vector作为heap容器,heap经常作为priority queue。

    当向heap中插入元素时,插入到末尾,“向上维护”即可:指的是把插入结点与其父结点比较,如果不符合堆得要求则交换,再向上维护其父结点……

    下图是push_heap的示意图。

    template <class RandomAccessIterator>
    inline void push_heap(RandomAccessIterator first, RandomAccessIterator last) {
    	// 注意,调用该函数时候,新元素位于最后一个位置(last-1)。
    	__push_heap_aux(first, last, distance_type(first), value_type(first));
    }
     
    template <class RandomAccessIterator, class Distance, class T>
    inline void __push_heap_aux(RandomAccessIterator first,
    	RandomAccessIterator last, Distance*, T*) {
    	__push_heap(first, Distance((last - first) - 1), Distance(0),
    		T(*(last - 1)));
    	// (last-first)–1代表新元素的索引,0是堆首的索引,*(last - 1)是新加入的值
    }
     
    template <class RandomAccessIterator, class Distance, class T>
    void __push_heap(RandomAccessIterator first, Distance holeIndex,
    	Distance topIndex, T value) {
    	Distance parent = (holeIndex - 1) / 2;	// 找出父節點
    	while (holeIndex > topIndex && *(first + parent) < value) {
    		// 尚未到达顶端,且父节点小于新值
    		// 由于以上使用 operator<,可知 STL heap 是max-heap
    		*(first + holeIndex) = *(first + parent);	// 令洞值为父值
    		holeIndex = parent; // percolate up:调整洞号,向上提升至父节点。
    		parent = (holeIndex - 1) / 2;	// 新洞的父节点
    	}    // 持续至顶端,或满足 heap 的次序特性为止。
    	*(first + holeIndex) = value;	// 令洞值为新值。
    }

    push_heap的用法是输入迭代器对,并且保证[first,last-1)是最大堆,*(last-1)是新加入的元素。push_heap调用辅助函数__push_heap_aux。至于为什么需要这个辅助函数了?应该是为了提取出distance_type和value_type吧,这两个内联函数的定义,可以参考stl源码剖析迭代器的那章。下面来思考真正的实现函数__push_heap。这个函数需要新加入元素位置holeIndex和堆首位置topIndex,另外还有保存好的新加入值。算法的过程很简单,就是上溯holeIndex,找到真正满足条件的位置(无法继续上回溯),然后把value放入该位置即可。

    当在heap取出元素时,把末尾元素放到Heap头,"向下维护“即可:指的是父结点与孩子结点比较,如果不满足要求,与较大(较小)一个交换,再维护交换的孩子结点……

    pop_heap实际上是一个相反的过程。实现思路是将堆大小加一后,再找出最后一个元素应该放入的位置holeIndex,最后再加入这个值。示意图如下:

    template <class RandomAccessIterator>
    inline void pop_heap(RandomAccessIterator first, RandomAccessIterator last) {
    	__pop_heap_aux(first, last, value_type(first));
    }
     
    template <class RandomAccessIterator, class T>
    inline void __pop_heap_aux(RandomAccessIterator first,
    	RandomAccessIterator last, T*) {
    	__pop_heap(first, last - 1, last - 1, T(*(last - 1)), distance_type(first));
    	// pop动作的結果为底层容器的第一個元素。因此,首先设定欲调整值为尾值,然后將首值調至 
    	// 尾节点(所以以上將迭代器result设为last-1)。然后重整 [first, last-1),
    	// 使之重新成一個合格的 heap。
    }
     
    template <class RandomAccessIterator, class T, class Distance>
    inline void __pop_heap(RandomAccessIterator first, RandomAccessIterator last,
    	RandomAccessIterator result, T value, Distance*) {
    	*result = *first; // 設定尾值为首值,于是尾值即是結果,
    	// 可由调用底层容器之 pop_back() 取出尾值。
    	__adjust_heap(first, Distance(0), Distance(last - first), value);
    	// 以上欲重新調整 heap,洞号为 0,欲調整值为value。
    }
     
    template <class RandomAccessIterator, class Distance, class T>
    void __adjust_heap(RandomAccessIterator first, Distance holeIndex,
    	Distance len, T value) {
    	Distance topIndex = holeIndex;
    	Distance secondChild = 2 * holeIndex + 2;	// 洞节点之右子节点
    	while (secondChild < len) {
    		// 比较洞节点之左右兩个子值,然后以 secondChild 代表较大子节点。
    		if (*(first + secondChild) < *(first + (secondChild - 1)))
    			secondChild--;
    		// Percolate down:令较大大子值为洞值,再令洞号下移至较大子节点处。
    		*(first + holeIndex) = *(first + secondChild);
    		holeIndex = secondChild;
    		// 找出新洞节点的右子节点
    		secondChild = 2 * (secondChild + 1);
    	}
     
    	if (secondChild == len) { // 沒有右子节点,只有左子节点
    		// Percolate down:令左子值为洞值,再令洞号下移至左子节点处。
    		*(first + holeIndex) = *(first + (secondChild - 1));
    		holeIndex = secondChild - 1;
    	}
     
    	// 將欲调整值填入目前的洞号內。注意,此時肯定滿足次序特性。
    	// 依侯捷之见,下面直接改為 *(first + holeIndex) = value; 应该可以。
    	__push_heap(first, holeIndex, topIndex, value);
    }

    类似于push_heap,pop_heap也是调用辅助函数__pop_heap_aux。__pop_heap_aux调用__pop_heap。__pop_heap调用__adjust_heap调整holeIndex,最终在holeIndex处放入value(原最后一个的值)。关键代码是__adjust_heap中的循环。循环的主要意思是将holeIndex不断下放,直到最底层。最后的if语句的意思是,如果最底层有左子节点,而没有右子节点,那么最终位置肯定是这个左子节点。最后一句代码的意思是加入value到holeIndex,由于已经调整完毕,所以一个赋值操作也可以达到要求,参见侯捷注释。

    sort_heap就比较简单了,不断将极值移动到末尾,不断pop_heap。

    // 以下這個 sort_heap() 不允許指定「大小比較標準」
    template <class RandomAccessIterator>
    void sort_heap(RandomAccessIterator first, RandomAccessIterator last) {
    	// 以下,每執行一次 pop_heap(),極值(在STL heap中為極大值)即被放在尾端。
    	// 扣除尾端再執行一次 pop_heap(),次極值又被放在新尾端。一直下去,最後即得
    	// 排序結果。
    	while (last - first > 1)
    		pop_heap(first, last--); // 每執行 pop_heap() 一次,操作範圍即退縮一格。
    }

    最后要将的是make_heap,即将一个迭代器对里面的内容构造为最大堆。代码如下:

    // 將 [first,last) 排列為一個 heap。
    template <class RandomAccessIterator>
    inline void make_heap(RandomAccessIterator first, RandomAccessIterator last) {
    	__make_heap(first, last, value_type(first), distance_type(first));
    }
     
    // 以下這組 make_heap() 不允許指定「大小比較標準」。
    template <class RandomAccessIterator, class T, class Distance>
    void __make_heap(RandomAccessIterator first, RandomAccessIterator last, T*,
    	Distance*) {
    	if (last - first < 2) return;	// 如果長度為 0 或 1,不必重新排列。
    	Distance len = last - first;
    	// 找出第一個需要重排的子樹頭部,以 parent 標示出。由於任何葉節點都不需執行 
    	// perlocate down,所以有以下計算。parent 命名不佳,名為 holeIndex 更好。
    	Distance parent = (len - 2) / 2;
     
    	while (true) {
    		// 重排以 parent 為首的子樹。len 是為了讓 __adjust_heap() 判斷操作範圍
    		__adjust_heap(first, parent, len, T(*(first + parent)));
    		if (parent == 0) return;	// 走完根節點,就結束。
    		parent--;					// (即將重排之子樹的)頭部向前一個節點
    	}
    }

     

    展开全文
  • SHALLOW HEAP和RETAINED HEAP

    2019-01-17 20:41:41
    SHALLOW HEAP:对象自身占用的内存大小; Shallow heap of an object is its size in the memory. RETAINED HEAP:对象能够被回收的内存大小,包括了直接引用和间接引用占用的内存; Retained heap is the ...
  • heapdump分析工具HeapAnalyzer

    热门讨论 2014-02-10 10:38:56
    heapdump分析工具------HeapAnalyzer: 2014年1月最新发布 用法: 在命令行执行 java -Xmx500m -jar ha453.jar
  • heap and heap sort

    2016-06-26 17:25:34
    heap定义,排序,堆排序c++源代码
  • 一、概念 堆可以看做一个完全二叉树,...make_heap: 时间复杂度为O(N) push_heap: 时间复杂度为O(logN) pop_heap: 时间复杂度为O(logN) sort_heap: 时间复杂度为O(NlogN) 二、代码 // range heap example #...
  • diff pprof heap

    2021-02-08 14:41:14
    dump heap curl -s http://127.0.0.1:8080/debug/pprof/heap > 1231.heap 休息十分钟 curl -s http://127.0.0.1:8080/debug/pprof/heap > 1241.heap diff go tool pprof --http :9090 --base 1231.heap 1241...
  • 本文介绍如何使用STL里的heap(堆)算法。第一次接触heap这种数据结构是在大学的数据结构教材上,它是一棵完全二叉树。在STL中,heap是算法的形式提供给我们使用的。包括下面几个函数: make_heap: 根据指定的...
  • Heap可被视为一个以序列式集合实现而成的二叉树,具有两大性质: 1.第一个元素总是最大或最小 2.总是能够在对数时间内增加或移除一个元素 为了处理heap,STL提供了4个算法: 1.make_heap()将区间内的元素转化为heap. ...
  • 理解shallow heap 和 retained heap

    万次阅读 2017-07-04 14:56:16
    heap 和 retained heap (有时候叫shallow size 和 retained size)。 shallow heap 比较好理解(好理解不代表好计算),直译就是浅层堆,其实就是这个对象实际占用的堆大小。 retained heap 比较...
  • C++STL算法提供make_heap, push_heap和pop_heap等算法,它们作用于随机存取迭代器。它们将迭代器当做数组的引用,并做出array-to-heap的转换。STL中默认这个算法为最大堆(max_heap)。 make_heap make_heap 的功能...
  • Heap Sort

    2020-10-05 03:01:21
    Heap Sort is an improvement to direct selection sort.From previous discussion,it can be seen that Using direct selection sort,in order to find out the smallest keyword among n keywords,n-1 comparisons...
  • heap(max-heap最大堆、min-heap最小堆)

    万次阅读 2018-08-16 10:24:14
    所谓binary heap就是一种完全二叉树,也就是说,整颗binary tree除了最底层的叶子节点之外,是填满的,而最底层的叶节点由左至右又不得有空隙。 完全二叉树整棵树内没有任何节点漏洞,这带来一个好处:我们可以...
  • heap并不属于STL容器组件,它分为 max heap 和min heap,在缺省情况下,max-heap是优先队列(priority queue)的底层实现机制。 而这个实现机制中的max-heap实际上是以一个vector表现的完全二叉树(complete binary...
  • C++中堆的应用:make_heap, pop_heap, push_heap, sort_heap

    万次阅读 多人点赞 2016-07-26 08:03:14
    C++中堆的应用:make_heap, pop_heap, push_heap, sort_heap, priority_queuemake_heap, pop_heap, push_heap, sort_heap都是标准算法库里的模板函数,用于将存储在vector/deque 中的元素进行堆操作,对不愿自己写...
  • heap并不属于STL容器组件,它分为 max heap 和min heap,在缺省情况下,max-heap是优先队列(priority queue)的底层实现机制。 而这个实现机制中的max-heap实际上是以一个vector表现的完全二叉树(complete binary...
  • 一、push_heap 头文件algorithm default (1) template &amp;lt;class RandomAccessIterator&amp;gt; void push_heap (RandomAccessIterator first, RandomAccessIterator last); custom (2) template &...
  • Binary Heap

    2015-11-05 21:58:40
    Priority Queue & Heap
  • 关于Heap Dump

    千次阅读 2019-04-08 22:58:48
    关于Heap DumpHeap Dump是什么?Heap Dump也叫堆转储文件,是一个Java进程在某个时间点上的内存快照。Heap Dump是有着多种类型的。不过总体上heap dump在触发快照的时候都保存了java对象和类的信息。通常在写heap du...
  • heap操作

    2015-10-08 15:55:43
    使用STL中的make_heap, push_heap, pop_heap, sort_heap进行对操作不用每次都自己写建立堆,调整堆和堆排序的代码了! make_heap(): 根据输入的迭代器,把其范围内的元素建立堆,默认是大顶堆(less()) push_heap...
  • 这个是因为 Android系统对 dalvik 的 vm heapsize 作了硬性限制,当 java 进程申请的 java 空间超过阈值时,就会抛出OOM异常(这个阈值可以是48 M、24 M、16 M等,视机型而定),可以通过adb shell getprop 或者 ...
  • std::pop_heap是一个实现快排的库将front(即第一个最大元素)移动到end的前部,同时将剩下的元素重新构造成(堆排序)一个新的heap。时间复杂度是: (2*log(last - first))例如:#include &lt;iostream&gt; #...
  • Heap

    2015-07-22 11:51:27
    Heap 堆, 数组实现
  • make_heap()是生成一个堆,大顶堆或小顶堆 make_heap(_RAIter,_RAIter) 默认生成大顶堆 make_heap(_RAIter,_RAIter,_Compare) _Compare有两种参数,一种是greater(生成小顶堆),一种是less(生成大顶堆) push_...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 68,790
精华内容 27,516
关键字:

heap