二叉堆的实现 && 海量数据中堆的应用

Knuth学徒

首先介绍下什么是堆，这里的堆指的是一种数据结构, 它的用途很广泛，包括排序，包括求N个元素中的最小的k个元素等。。。

      堆是一种树形结构，它是一棵完全二叉树，其中堆又分为最小堆和最大堆。

      最小堆：每个节点的键值都小于它的子树中的所有节点，所以最小堆的根节点的键值是整个堆中最小的。

      最大堆：每个节点的键值都大于它的子树中的所有节点，所以最大堆的根节点的键值是整个堆中最大的。

      于是，我们利用最大（小）堆的性质，可以在O(1)时间内得到n个元素中最小的值。

      现在，我以最小堆为例，介绍一下它的实现方式：

     用C++的类对heap进行封装：

     MinHeap.h文件：

1.      class MinHeap{
   
2.             private:
   
3.                    int count;               //当前堆中的元素个数
   
4.                    int val [MAX];     
   
5.                      //用一维数组存储堆，其中节点 i 的左孩子是 2*i ,右孩子是 2*i + 1 ,根节点的键值是 val [1]
   
6.                    void down(int position);     //最小堆的调整函数
   
7.                    //void up(int position)        最大堆的调整函数
   
8.             public:
   
9.                   MinHeap();                       //构造函数
   
10.                   void Insert(int data );       //将data插入堆中
    
11.                   int  Top_Remove() ;        //返回堆顶元素，并把堆顶元素删去，重新调整堆
    
12.                   bool  is_empty();            //返回堆是否为空，空则为 true，非空则为 false
    
13.                   int size();                        //返回当前堆的大小——堆中元素的个数
    
14.      };

复制代码

MinHeap.cpp 文件:

1.     //这里的代码风格借鉴了 Nisy老师上次共享的 DebuggerVC代码中的风格,好的代码风格就应该模仿。
   
2.      ///////////////////////////////////////////////////////////
   
3.      //     函数名：MinHeap()
   
4.      //     描述：构造函数,生成一个空堆
   
5.      //     参数：None
   
6.      //     前提：None
   
7.      //     用法：MinHeap  对象名
   
8.      ///////////////////////////////////////////////////////////
   
9.      MinHeap :: MinHeap(){
   
10.                count = 0;
    
11.      }
    
12.      
    
13.      ///////////////////////////////////////////////////////////
    
14.      //     函数名：is_empty()
    
15.      //     描述：判断堆是否为空
    
16.      //     参数：None
    
17.      //     前提：None
    
18.      //     用法：对象名.is_empty()
    
19.      ///////////////////////////////////////////////////////////
    
20.      bool  MinHeap :: is_empty(){
    
21.                  return (count == 0);
    
22.      }
    
23. 
    
24.      ///////////////////////////////////////////////////////////
    
25.      //     函数名：size()
    
26.      //     描述：返回堆的大小
    
27.      //     参数：None
    
28.      //     前提：None
    
29.      //     用法：对象名.size()
    
30.      ///////////////////////////////////////////////////////////
    
31.     int  MinHeap :: size(){
    
32.                    return count;
    
33.     }
    
34. 
    
35. 
    
36.      ///////////////////////////////////////////////////////////
    
37.      //     函数名：Insert()
    
38.      //     描述：往堆中插入一个元素，并重新调整堆结构
    
39.      //     参数：Data 表示插入元素的键值
    
40.      //     前提：None
    
41.      //     用法：对象名.Insert( xx )
    
42.      ///////////////////////////////////////////////////////////
    
43.      void MinHeap :: Insert( int data)
    
44.      {
    
45.                     val [++ count ] = data;       //先将元素放入堆尾
    
46.                     int  p = count ;                    //调整用指针
    
47.                     while(p > 1) {                      //在到达根节点之前
    
48.                               if( val[ p>>1 ] > val [p] ){     //如果p的父节点键值＞p,进行交换
    
49.                                          int tmp = val [p] ;
    
50.                                          val [p] = val [ p>>1 ] ;
    
51.                                          val[p>>1] = tmp;
    
52.                                          p >> = 1;                //指针向上移
    
53.                              }
    
54.                              else break;                          //如果没有破坏堆结构直接跳出。
    
55.                     }
    
56.       }
    
57. 
    
58.               
    
59.      ///////////////////////////////////////////////////////////
    
60.      //     函数名：down(int position)
    
61.      //     描述：将当前破坏了的堆 通过下降调整为堆
    
62.      //     参数：position 表示需要调整的位置
    
63.      //     前提：None
    
64.      //     用法：None
    
65.      ///////////////////////////////////////////////////////////   
    
66.      void MinHeap :: down(int position)
    
67.      {
    
68.                while( (position << 1) <= size )   //如果位置还没下降到叶子节点
    
69.                {
    
70.                           int tmp = position << 1;
    
71.                            if( ( position << 1 ) + 1 <= size && val[ (position<<1)+1] < val[tmp] )
    
72.                                     //如果当前节点的右孩子小于当前节点的左孩子
    
73.                                            tmp = ( possition<<1 )+ 1;
    
74.                            if( val [tmp] < val[position] ) {
    
75.                                     //如果当前节点的右孩子 小于当前节点
    
76.                                     int temp = val [tmp] ;
    
77.                                     val [tmp ] = val[position];
    
78.                                     val [position ] = temp;
    
79.                                     position = tmp;
    
80.                          }
    
81.                          else break;
    
82.                }
    
83.      }
    
84. 
    
85. 
    
86.      ///////////////////////////////////////////////////////////
    
87.      //     函数名：Top_Remove()
    
88.      //     描述：返回堆顶元素，并删除之，再重新调整堆结构
    
89.      //     参数：None
    
90.      //     前提：None
    
91.      //     用法：对象名.Top_Remove()
    
92.      ///////////////////////////////////////////////////////////
    
93.      int MinHeap :: Top_Remove(){
    
94.                    int temp = val[1] ; //保存堆顶元素
    
95.                    val [1] = val [ count];
    
96.                    val [count ] = temp;
    
97.                    count --;
    
98.                    down(1);  调整整个堆
    
99.                    return val[count + 1];
    
100.     }
     

复制代码

++++++++++++++++++++++++++++++++++++++++++++++++++++++++
    +            以上给出了一个最小堆的具体实现方式，下面给出堆的实际应用
    ++++++++++++++++++++++++++++++++++++++++++++++++++++++++

     一、堆排序：
             因为我们可以在O(1)时间复杂度内求出n个元素中的最值，于是我们就可以用它来排序。

             思想是，将待排序元素 a[MAX] 一一插入到这个堆中，那么，堆顶元素永远是最小的，于是，我们把堆顶元素放到最后，然后用新插入的元素来代替，接着重新调整堆，这样逐步迭代后，我们就可以得到一个 从大到小的有序序列。
             时间复杂度： T(n) = N*O(logN) 插入时间  = O(NlogN)
            与快速排序算法的时间复杂度都很高，所以堆排序也是一种很好的稳定排序方式，它不太会像快排那样退化成O(n^2)

    二、求出海量数据中的最小的n个元素——这里要用到最大堆，和最小堆的实现方式正好相反。

           如果有海量的数据,求前n个元素并不简单，如果要先排序的话，时间复杂度非常高，这里就可以用到堆的思想。

           对海量数据进行一次线性的扫描，然后把每个元素插入最大堆中，如果下一个元素小于堆顶元素，那么把堆顶元素删去，用下一个元素来代替，然后重新调整堆，再继续插入。

        这样，最后堆中的n个元素就是最小的n个元素。

  +++++++++++++++++++++++++++后记++++++++++++++++++++++++++

       堆还有更多的用途，我这里只起到一个抛砖引玉的作用。      

       转载时请注明出处。

+++++++++++++++++++++++++++++++++++++++++++++++++++++++++

Knuth学徒

我上面说的堆 别和程序中的堆栈搞起来。。。一个是数据结构ADT，一个是系统的内存空间

a1250377248

飘云真是太好了

飘云

人才！不去分析XX，真是浪费了，你懂的~~

Knuth学徒

回复 4# 飘云


    谢谢老大赞赏…… 最近比较忙, 抽空看了几个破解视频, 觉得破解也是很有意思的。