数据结构与算法分析学习笔记(5)

堆是一颗被完全填满的二叉树，有可能的例外是在底层，底层的元素被从左到右被填满；

一颗高为h的完全二叉树有2^h到2^h+1-1个节点；完全二叉树的高是¸logN¸；

因为完全二叉树很有规律，所以它可以用一个数组表示而不需要指针。对于数组实现上，任一位置i上的元素，其左儿子在2i上，右儿子在2i+1中，它的父亲在¸i/2¸上。

一个堆结构将由一个数组，一个代表最大值的整数以及当前的堆大小组成。

 1 //优先队列的声明
 2 #ifndef _BinHeap_H
 3 
 4 struct HeapStruct;
 5 typedef struct HeapStruct *PriorityQueue;
 6 PriorityQueue Initialize(int MaxElements);
 7 void Destroy(PriorityQueue H);
 8 void MakeEmpty(PriorityQueue H);
 9 void Insert(ElementType X,PriorityQueue H);
10 ElementType DeleteMin(PriorityQueue H);
11 ElementType FindMin(PriorityQueue H);
12 int IsEmpty(PriorityQueue H);
13 int IsFull(PriorityQueue H);
14 
15 #endif
16 
17 struct HeapStruct
18 {
19     int Capacity;
20     int Size;
21     ElementType *Elements;
22 };
23 //初始化
24 PriorityQueue Initialize(int MaxElements)
25 {
26     PriorityQueue H;
27     if(MaxElements<MinPQsize)
28         Erro("Priority Queue Size is too small");
29     H=malloc(Sizeof(struct HeapStruct));
30     if(NULL==H)
31         FataErro("Out of space!");
32     H->Elements=malloc((MaxElements+1)*sizeof(ElementType));
33     if(H->Element==NULL)
34         FataErro("Out of Space~");
35     H->Capacity=MaxElements;
36     H->Size=0;
37     H->Element[0]=MinData;
38     
39     return H;
40 }
41 
42 //插入过程
43 void Insert(ElementType X,PriorityQueue H)
44 {
45     int i;
46     if(IsFull(H))
47     {
48         Error("Priority queue is full");
49         return ;
50     }
51     for(i=++H->Size;H->Elements[i/2]>X;i=i/2)
52         H->Elements[i]=H->Elements[i/2];
53     H->Elements[i]=X;
54 }
55 //删除最小过程
56 ElementType DeleteMin(PriorityQueue H)
57 {
58     int i,child;
59     ElementType MinElement,LastElement;
60     if(IsEmpty(H))
61     {
62         Error("priority queue is empty");
63         return H->Elements[0];
64     }
65     MinElements=H->Elements[1];
66     LastElement=H->Elements[H->Size--];
67     for(i=1;i*2<=H-Size;i=child)
68     {
69         Child=i*2;
70         if(Child!=H->Size&&H->Elements[Child+1]<H->Elements[Child])
71         Child++;
72         if(LastElement>H->Elements[Child])
73             H->Elements[i]=H->Elements[Child];
74         else
75             break;
76     }
77     H->ELements[i]=LastElement;
78     return MinElement;
79 }

定理：包含2^h+1-1个节点高位h的理想二叉树的节点高度的和为2^h+1-1-(h+1)。

典型利用：

选择问题：输入N个元素以及整数K，这N个元素的集可以是全序的，找出第K个最大的元素；

算法一、

　　把这些元素排序，返回第K个值,通过各种排序算法;

算法二、

　　将K个元素读入数组，并将其排序，从大到小，最小的元素在第K个位置上。然后一个一个处理剩余的元素。当一个元素处理时，它先与数组中的第K个数比较，如果该元素大，将第K个数删除，将它插入到剩余的K-1个队列中，算法结束时，数组上第K个位置上的元素就为所求；该算法的时间复杂度为O（N*K）；

注意：对于任意的K,我们可以求解对称问题，找出第（N-K+1）个最小元素。从而中位数K=N/2是时间使用最多的所求元素；

算法三、

　　将N个元素建堆，执行K次DeleteMax操作。

Edit By SolarJupiter

数据结构与算法分析 学习笔记(5)

数据结构与算法分析学习笔记(5)