AI 助理
备案控制台
开发者社区 人工智能 文章 正文

数据结构——堆(转载)

2015-09-30 960
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 堆常用来实现优先队列，在这种队列中，待删除的元素为优先级最高（最低）的那个。在任何时候，任意优先元素都是可以插入到队列中去的，是计算机科学中一类特殊的数据结构的统称 一、堆的定义 最大（最小）堆是一棵每一个节点的键值都不小于（大于）其孩子（如果存在）的键值的树。

堆常用来实现优先队列，在这种队列中，待删除的元素为优先级最高（最低）的那个。在任何时候，任意优先元素都是可以插入到队列中去的，是计算机科学中一类特殊的数据结构的统称

一、堆的定义

最大（最小）堆是一棵每一个节点的键值都不小于（大于）其孩子（如果存在）的键值的树。大顶堆是一棵完全二叉树，同时也是一棵最大树。小顶堆是一棵完全完全二叉树，同时也是一棵最小树。

注意：

  • 堆中任一子树亦是堆。
  • 以上讨论的堆实际上是二叉堆(Binary Heap)，类似地可定义k叉堆。

下图分别给出几个最大堆和最小堆的例子：

二、支持的基本操作

堆支持以下的基本操作:

  • build: 建立一个空堆；
  • insert: 向堆中插入一个新元素；
  • update：将新元素提升使其符合堆的性质；
  • get：获取当前堆顶元素的值；
  • delete：删除堆顶元素；
  • heapify：使删除堆顶元素的堆再次成为堆。

某些堆实现还支持其他的一些操作，如斐波那契堆支持检查一个堆中是否存在某个元素。

三、堆的应用

1.堆排序

 堆排序(HeapSort)是一树形选择排序。
    　堆排序的特点是：在排序过程中，将R[l..n]看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系【参见二叉树的顺序存储结构】，在当前无序区中选择关键字最大(或最小)的记录。
优点直接选择排序中，为了从R[1..n]中选出关键字最小的记录，必须进行n-1次比较，然后在R[2..n]中选出关键字最小的记录，又需要做n-2次比较。事实上，后面的n-2次比较中，有许多比较可能在前面的n-1次比较中已经做过，但由于前一趟排序时未保留这些比较结果，所以后一趟排序时又重复执行了这些比较操作。
    　堆排序可通过树形结构保存部分比较结果，可减少比较次数。
堆排序利用了大根堆(或小根堆)堆顶记录的关键字最大(或最小)这一特征，使得在当前无序区中选取最大(或最小)关键字的记录变得简单。
（1）、用大根堆排序的基本思想
  • 先将初始文件R[1..n]建成一个大根堆，此堆为初始的无序区
  • 再将关键字最大的记录R[1](即堆顶)和无序区的最后一个记录R[n]交换，由此得到新的无序区R[1..n-1]和有序区R[n]，且满足R[1..n-1].keys≤R[n].key
  • 由于交换后新的根R[1]可能违反堆性质，故应将当前无序区R[1..n-1]调整为堆。然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换，由此得到新的无序区R[1..n-2]和有序区R[n-1..n]，且仍满足关系R[1..n-2].keys≤R[n-1..n].keys，同样要将R[1..n-2]调整为堆。直到无序区只有一个元素为止。
（2）、大根堆排序算法的基本操作：
  • 初始化操作：将R[1..n]构造为初始堆；
  • 每一趟排序的基本操作：将当前无序区的堆顶记录R[1]和该区间的最后一个记录交换，然后将新的无序区调整为堆(亦称重建堆)。
  注意：
  • 只需做n-1趟排序，选出较大的n-1个关键字即可以使得文件递增有序。
  • 用小根堆排序与利用大根堆类似，只不过其排序结果是递减有序的。堆排序和直接选择排序相反：在任何时刻，堆排序中无序区总是在有序区之前，且有序区是在原向量的尾部由后往前逐步扩大至整个向量为止。
（3）、算法实现
  1. ////////////////////////////////////////////////////////////////////   
  2. //堆排序  
  3. template <class T>  
  4. void Sort::HeapSort(T arr[], int len){  
  5.     int i;   
  6.       
  7.     //建立子堆   
  8.     for(i = len / 2; i >= 1; i--){  
  9.         CreateHeap(arr, i, len);  
  10.     }  
  11.       
  12.     for(i = len - 1; i >= 1; i--){  
  13.         buff = arr[1];  
  14.         arr[1] = arr[i + 1];  
  15.         arr[i + 1] = buff;   
  16.           
  17.         CreateHeap(arr, 1, i);   
  18.     }  
  19. }   
  20.   
  21.   
  22. //建立堆   
  23. template <class T>  
  24. void Sort::CreateHeap(T arr[], int root, int len){  
  25.     int j = 2 * root;                   //root's left child, right (2 * root + 1)   
  26.     T temp = arr[root];  
  27.     bool flags = false;   
  28.       
  29.     while(j <= len && !flags){  
  30.         if(j < len){  
  31.             if(arr[j] < arr[j + 1]){     // Left child is less then right child   
  32.                 ++j;                // Move the index to the right child   
  33.             }     
  34.         }  
  35.           
  36.         if(temp < arr[j]){  
  37.             arr[j / 2] = arr[j];  
  38.             j *= 2;   
  39.         }else{  
  40.             flags = true;   
  41.         }   
  42.     }   
  43.    arr[j / 2]  = temp;   
  44. }   

2.选择前k个最大（最小）的数

思想：在一个很大的无序数组里面选择前k个最大（最小）的数据，最直观的做法是把数组里面的数据全部排好序，然后输出前面最大（最小）的k个数据。但是，排序最好需要O(nlogn)的时间，而且我们不需要前k个最大（最小）的元素是有序的。这个时候我们可以建立k个元素的最小堆(得出前k个最大值)或者最大堆(得到前k个最小值)，我们只需要遍历一遍数组，在把元素插入到堆中去只需要logk的时间，这个速度是很乐观的。利用堆得出前k个最大（最小）元素特别适合海量数据的处理。

代码：

    1. typedef multiset<int, greater<int> >            intSet;  
    2. typedef multiset<int, greater<int> >::iterator  setIterator;  
    3.   
    4. void GetLeastNumbers(const vector<int>& data, intSet& leastNumbers, int k)  
    5. {  
    6.     leastNumbers.clear();  
    7.   
    8.     if(k < 1 || data.size() < k)  
    9.         return;  
    10.   
    11.     vector<int>::const_iterator iter = data.begin();  
    12.     for(; iter != data.end(); ++ iter)  
    13.     {  
    14.         if((leastNumbers.size()) < k)  
    15.             leastNumbers.insert(*iter);  
    16.   
    17.         else  
    18.         {  
    19.             setIterator iterGreatest = leastNumbers.begin();  
    20.   
    21.             if(*iter < *(leastNumbers.begin()))  
    22.             {  
    23.                 leastNumbers.erase(iterGreatest);  
    24.                 leastNumbers.insert(*iter);  
    25.             }  
    26.         }  
    27.     }  
    28. } 
文章标签：
算法
移动开发
存储
关键词：
数据结构堆
技术让梦想更伟大-李肖遥
目录
相关文章
进步`于辰
|
1月前
|
存储 算法 Java
散列表的数据结构以及对象在JVM堆中的存储过程
本文介绍了散列表的基本概念及其在JVM中的应用，详细讲解了散列表的结构、对象存储过程、Hashtable的扩容机制及与HashMap的区别。通过实例和图解，帮助读者理解散列表的工作原理和优化策略。
进步`于辰
37 1
散列表的数据结构以及对象在JVM堆中的存储过程
ephemerals__
|
1月前
|
存储 搜索推荐 算法
【数据结构】树型结构详解 + 堆的实现（c语言）（附源码）
本文介绍了树和二叉树的基本概念及结构，重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树，常用于实现优先队列和高效的排序算法（如堆排序）。文章详细描述了堆的性质、存储方式及其实现方法，包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容，读者可以全面了解堆的原理和应用。
ephemerals__
67 16
神明木佑
|
2月前
|
存储 JavaScript 前端开发
为什么基础数据类型存放在栈中，而引用数据类型存放在堆中？
为什么基础数据类型存放在栈中，而引用数据类型存放在堆中？
神明木佑
83 1
2的n次方_
|
3月前
|
存储 Java
【数据结构】优先级队列（堆）从实现到应用详解
本文介绍了优先级队列的概念及其底层数据结构——堆。优先级队列根据元素的优先级而非插入顺序进行出队操作。JDK1.8中的`PriorityQueue`使用堆实现，堆分为大根堆和小根堆。大根堆中每个节点的值都不小于其子节点的值，小根堆则相反。文章详细讲解了如何通过数组模拟实现堆，并提供了创建、插入、删除以及获取堆顶元素的具体步骤。此外，还介绍了堆排序及解决Top K问题的应用，并展示了Java中`PriorityQueue`的基本用法和注意事项。
2的n次方_
61 5
【数据结构】优先级队列（堆）从实现到应用详解
平凡程序猿~
|
2月前
|
存储 算法 调度
数据结构--二叉树的顺序实现（堆实现）
数据结构--二叉树的顺序实现（堆实现）
平凡程序猿~
70 1
是店小二呀
|
2月前
|
存储 算法 分布式数据库
【初阶数据结构】理解堆的特性与应用：深入探索完全二叉树的独特魅力
【初阶数据结构】理解堆的特性与应用：深入探索完全二叉树的独特魅力
是店小二呀
56 1
阿客不是客
|
2月前
|
存储 算法
探索数据结构：分支的世界之二叉树与堆
探索数据结构：分支的世界之二叉树与堆
阿客不是客
26 0
GuGuStudy
|
2月前
|
存储 算法 Java
【用Java学习数据结构系列】用堆实现优先级队列
【用Java学习数据结构系列】用堆实现优先级队列
GuGuStudy
35 0
努力学习的小廉
|
2月前
|
存储 算法
【数据结构】二叉树——顺序结构——堆及其实现
【数据结构】二叉树——顺序结构——堆及其实现
努力学习的小廉
28 0
椰椰椰耶
|
2月前
【数据结构】大根堆和小根堆
【数据结构】大根堆和小根堆
椰椰椰耶
38 0