数据结构之——堆结构的实现

堆

堆是一个数组，可以被看成一个近似的完全二叉树，树上的每一个节点对应数组的每个元素。除了最底层外，该树是完全充满的，而且是从左向右填充。

堆又分为大根堆和小根堆
大根堆：父节点总是大于其子节点，
小根堆：父节点总是小于其子节点。
本文基于Java语言，使用数组实现一个堆结构及其操作。

堆结构实现 public class Heap {final int MAX = 999;// 定义最大容量999private int[] heap;private int size;/** * 初始化一个堆 * * @param a */public Heap(int a[]) {this.heap = new int[MAX];for (int i = 0; i < a.length; i++)heap[i + 1] = a[i];// 堆的下标从1开始this.size = a.length;// 建堆for (int i = this.size / 2; i >= 1; i--)max_Heapify(heap, i, size);}public int[] getHeap() {return heap;}public int getSize() {return size;}public void printHeap(int heap[], int size) {for (int i = 1; i <= size; i++)System.out.print(heap[i]);}public int getParent(int i) {// 获取节点i的父节点下标return i / 2;}public int getLeft(int i) {// 左孩子下标return 2 * i;}public int getRight(int i) {// 右孩子下标return 2 * i + 1;}/** * 调整堆结构，使得以i为根节点的子树满足堆结构 * * @param a * @param i * @param size 堆的大小 * @return */public int[] max_Heapify(int a[], int i, int size) {int left = getLeft(i);int right = getRight(i);int largest;// 找到i与其两个子节点中最大的，交换if (left <= size && a[i] < a[left]) {largest = left;} elselargest = i;if (right <= size && a[right] > a[largest])largest = right;if (largest != i) {exchange(a, i, largest);max_Heapify(a, largest, size);// 递归地调整，直到满足堆结构}return a;}/** * 利用最大堆的第一个元素一定是最大的这个特性，每次将最后一个元素与第一个元素交换，然后调整就可以获得最大值，第二大值.... * @param a * @param size * @return */public int[] heapSort(int a[],int size) {for(int i = size;i>=1;i--) {exchange(a,1,i);//交换最后一个元素与第一个元素size = size-1;max_Heapify(a,1,size);//每次都调整根节点}return a;}/** * 交换两个下标的元素值 * * @param a * @param x * @param y */public void exchange(int a[], int x, int y) {int tmp = a[x];a[x] = a[y];a[y] = tmp;}} 调试 public class HelloWorld {public static void main(String[] args) {int a[] = { 1, 2, 3, 4, 5, 6, 7 };Heap hp = new Heap(a);System.out.println("建堆后:");hp.printHeap(hp.getHeap(), hp.getSize());hp.heapSort(hp.getHeap(), hp.getSize());System.out.println("n排序后:");hp.printHeap(hp.getHeap(), hp.getSize());}}

运行结果

堆排序

思想：利用堆结构的特点，堆顶的元素值最大，所以我们每次都将堆顶的元素与堆底的元素交换，使size-1，然后重新调整堆结构，这时候的调整就不会影响到堆底的那个最大的元素了，直到堆的size=1时，就完成了排序。排序的顺序是从大到小确定元素的位置。

/** * 利用最大堆的第一个元素一定是最大的这个特性，每次将最后一个元素与第一个元素交换，然后调整就可以获得最大值，第二大值.... * @param a * @param size * @return */public int[] heapSort(int a[],int size) {for(int i = size;i>=1;i--) {exchange(a,1,i);//交换最后一个元素与第一个元素size = size-1;max_Heapify(a,1,size);//每次都调整根节点}return a;}

时间复杂度分析：max_Heapify()的时间复杂度是O(lgn)，排序算法中进行了n次运算，所以时间复杂度是O(nlgn)

用堆结构实现优先队列 队列

堆排序是个优秀的算法，但是实际应用中，快速排序的行能一般优于堆排序，尽管如此，堆这一数据结构仍有许多应用——作为高效的优先队列。和堆一样，优先队列也有两种形式，最大优先队列和最小优先队列。这里我关注于如何基于最大堆实现最大优先队列。

实现

在上面堆结构实现的基础上，再实现以下方法：

Maximum(S)：返回具有最大关键字的元素 public int Maximum(int a[], int size) {return a[1];} Extract-Max(S)：去掉并返回最大关键字的元素 /** * * @param heap * @param size * @return */public int Extract_max(int heap[], int size) {if (size < 1) {System.out.print("heap underflow");return -1;}int max = heap[1];// 获得最大值exchange(heap, 1, size);this.setSize(this.getSize() - 1);// 堆size-1max_Heapify(heap, 1, this.getSize());// 调整堆结构return max;} Insert(S,x)：把元素x插入到S中 /** * * @param heap * @param i * @param key */public void Increase_Key(int heap[], int i, int key) {if(key<heap[i]) System.out.print("new key is smaller than current key");heap[i] = key;while(i>1&&heap[getParent(i)]<heap[i]) {//如果更改后的key值比其父节点要大，就交换两个节点值exchange(heap,i,getParent(i));i = getParent(i);}} Increase-Kye(S,x,key)：将元素x的关键字的值增加到key /** * 插入一个元素，思路是现在堆的末尾加一个很小的数， * 然后利用上面已有的修改指定位置元素key值的方法将其值修改为制定的key值 * @param heap * @param key */public void Insert(int heap[],int key) {int a = -999;int size = this.getSize();heap[size+1]=a;this.setSize(size+1);Increase_Key(heap,size+1,key);} 调试 public class HelloWorld {public static void main(String[] args) {int a[] = { 1, 2, 3, 4, 5, 6, 7 };Heap hp = new Heap(a);System.out.println("建堆后:");hp.printHeap(hp.getHeap(), hp.getSize());System.out.print("n"+hp.Extract_max(hp.getHeap(), hp.getSize()));System.out.println("n出队列后:");hp.printHeap(hp.getHeap(), hp.getSize());hp.Increase_Key(hp.getHeap(), 3, 9);System.out.println("n将第三个元素的key值改为9后:");hp.printHeap(hp.getHeap(), hp.getSize());hp.Insert(hp.getHeap(),8);System.out.println("n插入一个key为8的元素后:");hp.printHeap(hp.getHeap(), hp.getSize());}} 结果