数据结构-结构与算法堆

优先级队列可以用有序数组来实现,这种做法的问题是,尽管删除最大数据项的时间复杂度为O(1),但是插入还是需要较长的O(N)时间,这是因为必须移动数组中平均一半的数据项以插入新数据项,并在完成插入后,数组依然有序。 这里介绍实现优先级队列的另一种结构:

堆。堆是一种树,并非java和C++等编译语言里的“堆”。由它实现的优先级队列的插入和删除的时间复杂度都是O(logN)。尽管这样删除的时间变慢了一些,但是插入的时间快的多了。当速度非常重要,且有很多插入操作是,可以选择堆来实现优先级队列。

堆有如下特点:

·它是完全二叉树。即除了树的最后一层节点不需要是满的外,其他的每一层从左到右都完全是满的。

·它常常用一个数组实现。用数组实现的完全二叉树中,节点的索引有如下特点(设该节点的索引为x): 它的父节点的索引为 (x-1) / 2; 它的左子节点索引为 2*x + 1;

它的右子节点索引为 2*x + 2。 ·堆中每个节点的关键字都大于(或等于)这个节点的子节点的关键字。这也是堆中每个节点必须满足的条件。所以堆和二叉搜索树相比,是弱序的。

向堆中插入数据,首先将数据项存放到叶节点中(即存到数组的最后一项),然后从该节点开始,逐级向上调整,直到满足堆中节点关键字的条件为止。 从堆中删除数据与插入不同,删除时永远删除根节点的数据,因为根节点的数据最大,删除完后,将最后一个叶节点移到根的位置,然后从根开始,逐级向下调整,直到满足堆中节点关键字的条件为止。具体的看下面的代码:

1
2
3
4
5
6
7
8
9
public class Heap { private Node[] heapArray; private int maxSize; private int currentSize; public Heap(int mx) { maxSize = mx; currentSize = 0; heapArray = new Node[maxSize]; } public boolean isEmpty() { return (currentSize == 0)? true : false; } public boolean isFull() { return (currentSize == maxSize)? true : false; } public boolean insert(int key) { if(isFull()) { return false; } Node newNode = new Node(key); heapArray[currentSize] = newNode; trickleUp(currentSize++); return true; } //向上调整 
public void trickleUp(int index) { int parent = (index - 1) / 2; //父节点的索引
Node bottom = heapArray[index]; //将新加的尾节点存在bottom中
while(index > 0 && heapArray[parent].getKey() < bottom.getKey()) { heapArray[index] = heapArray[parent]; index = parent; parent = (parent - 1) / 2; } heapArray[index] = bottom; } public Node remove() { Node root = heapArray[0]; heapArray[0] = heapArray[–currentSize]; trickleDown(0); return root; } //向下调整
public void trickleDown(int index) { Node top = heapArray[index]; int largeChildIndex; while(index < currentSize/2) { //while node has at least one child
int leftChildIndex = 2 * index + 1; int rightChildIndex = leftChildIndex + 1; //find larger child
if(rightChildIndex < currentSize && //rightChild exists?
heapArray[leftChildIndex].getKey() < heapArray[rightChildIndex].getKey()) { largeChildIndex = rightChildIndex; } else { largeChildIndex = leftChildIndex; } if(top.getKey() >= heapArray[largeChildIndex].getKey()) { break; } heapArray[index] = heapArray[largeChildIndex]; index = largeChildIndex; } heapArray[index] = top; } //根据索引改变堆中某个数据
public boolean change(int index, int newValue) { if(index < 0 || index >= currentSize) { return false; } int oldValue = heapArray[index].getKey(); heapArray[index].setKey(newValue); if(oldValue < newValue) { trickleUp(index); } else { trickleDown(index); } return true; } public void displayHeap() { System.out.println(“heapArray(array format): “); for(int i = 0; i < currentSize; i++) { if(heapArray[i] != null) { System.out.print(heapArray[i].getKey() + “ “); } else { System.out.print(“–”); } } } } class Node { private int iData; public Node(int key) { iData = key; } public int getKey() { return iData; } public void setKey(int key) { iData = key; } }
  • 版权声明: 本博客所有文章,未经许可,任何单位及个人不得做营利性使用!转载请标明出处!如有侵权请联系作者。
  • Copyrights © 2015-2020 翟天野

请我喝杯咖啡吧~