堆和优先队列
1 二叉堆和优先队列的概念
1.1 二叉堆
二叉堆是一个数组,它可以被看成一个近似的完全二叉树,树上每一个结点对应数组中的一个元素。除了最底层外,该树是完全充满的,而且是从左到右填充。表示堆的数组A包括两个属性:A.length给出数组元素的个数,A.heap_size表示有多少个堆元素存储在该数组中,这里,0<=A.heap_size<=A.length。
如下图所示:
堆可以分成两种:最大堆和最小堆。在最大堆中,任何节点的值都大于等于其孩子的值,故根节点是数组中的最大数所在节点。反之,最小堆中,任何节点的值都小于等于其孩子的值,故根节点是数组中最小值所在节点。
最小堆如下:
1.2 优先队列
优先队列是一种用来维护由一组元素构成的集合S的数据结构,其中的每一个元素都有一个相关的值,称为关键字。优先队列也分为两种:最大优先队列和最小优先队列。
一个最大优先队列支持以下操作:
•INSERT(S,x):把元素x插入集合S中;
•MAXIMUM(S):返回S中具有最大关键字的元素;
•EXTRACT_MAX(S):去掉并且返回S中的具有最大关键字的元素;
•INCREASE_KEY(S,x,k):将元素x的关键字值增加到k。
相应地,最小优先队列支持的操作包括INSERT、MINIMUM、EXTRAT_MIN和DECRESE_KEY。
2 堆的实现
2.1 堆的插入
由于二叉堆就是一个简单的一维Int数组,故不需要初始化,直接插入便可。
每次插入都将新数据放到数组的最后的位置,最小堆原理如图:
假设要在这个二叉堆里入队一个单元,键值为2,那只需在数组末尾加入这个元素,然后尽可能把这个元素往上挪,直到挪不动,经过了这种复杂度为Ο(logn)的操作,二叉堆还是二叉堆。
核心代码如下:
1 //A为该数组,i是新数据所在下标 2 void Insert(int A[], int i,int heap_size) 3 { 4 int j, temp; 5 6 temp = A[i]; 7 j = i / 2; //父结点 8 while (j >= 1 && i != 1) 9 { 10 if (A[j] <= temp) 11 break; 12 13 A[i] = A[j]; //把较大的子结点往下移动,替换它的子结点 14 i = j; 15 j = i / 2; 16 } 17 A[i] = temp; 18 heap_size ++; 19 }
2.2 堆的删除
按定义,堆中每次都只能删除第1个数据。为了便于重建堆,实际的操作是将最后一个数据的值赋给根结点,然后再从根结点开始进行一次从上向下的调整。调整时先在左右儿子结点中找最小的,如果父结点比这个最小的子结点还小说明不需要调整了,反之将父结点和它交换后再考虑后面的结点。相当于从根结点将一个数据的“下沉”过程。
下面给出代码:
1 //先进行调整 2 void MinHeapify(int A[],int i,int heap_size) 3 { 4 int l = 2*i; 5 int r = 2*i+1; 6 int minimum; 7 if(l <= heap_size && A[l] < A[i]) 8 minimum = l; 9 else 10 minimum = i; 11 if(r <= heap_size && A[r] > A[minimum]) 12 minimum = r; 13 if(minimum!= i) 14 { 15 swap(A[i],A[minimum]); 16 MinHeapify(minimum,heapsize); 17 } 18 } 19 20 //然后删除 21 void Delete(int A[],int heap_size) 22 { 23 Swap(A[1],A[heap_size]); 24 heap_size --; 25 MinHeapify(A,1,heap_size); 26 }