最小堆

堆的定义是：n个元素的序列{k₁,k₂,…,k_n}，当且仅当满足如下关系时被成为堆

1. K_i <= k_2i 且 k_i <= k_2i-1        或者
2. K_i >= k_2i 且 k_i >= k_2i-1  (i = 1,2,…[n/2])

 

当满足(1)时，为最小堆，当满足(2)时，为最大堆。

 

 

若将此序列对应的一维数组堪称是一个完全二叉树，则2i和2i+1个节点分别是节点i的左右子节点。

如下为一个最大堆：

 

下面以最小堆为例说明堆的输出：

 

　　图1为一个最小堆，当最小节点根节点13输出后，将最后一个节点97作为根节点，移到顶端，如图2. 然后要对堆进行调整。比较此完全树的根节点与其两个子节点大小，因为27 < 38 < 97，所以27是三个节点里最小的，将节点27与根节点97交换。此时以97替代27而产生的右子树为一个新的堆，再以97为根节点，对此最小堆进行调整，同理，知道要将97与49交换，得到图3的完全树。此时以97代替49为根节点的右子树为一个新堆，再对此堆做同样的操作，因为此完全树已经是最小堆，所以可以停止操作，堆的调整完毕。此时再将根节点，对的最小值输出，并进行同样的调整，可以得到如图4的新堆。这个过程被称为“筛选”。

 

同样以最小堆说明堆的初始化：

　　从一个无序序列初始化为一个堆的过程就是一个反复“筛选”的过程。由完全二叉树的性质可以知，一个有n个节点的完全二叉树的最后一个非叶节点是节点[n/2]，堆的初始化过程就从这个[n/2]节点开始。上图为如下无序数组的初始化：

　　　　{49,38,65,97,76,13,27,50}

　　首先，未处理的数组对应的堆为图1模样。从第四个节点开始（[8/2]=4），因为50 < 97，故要交换两节点，交换后还要继续对其新的左子树进行类似输出后那样的筛选。易见其左子树只有节点97，已经为最佳情况，故可以继续堆的初始化，如图2。再考虑第三个节点，因为13 < 27 < 65，即节点13为当前的最小节点，故与节点65交换，并对新的左子树进行筛选，其也为最佳情况，故可继续堆的初始化，结果如图3。然后考虑第二个节点，因为38 < 50 < 76，故已经为最优情况，不用调整。最后再考虑第一个节点，根节点。因为 13 < 38 < 49，故需要将根节点49与其右孩子节点13交换，交换后还要继续对其新的右子树进行类似输出后那样的筛选，可见右子树还需要调整，因为 27 < 49 < 65,故将节点49与节点27交换。此时已经处理完了根节点，初始化结束。最终结果如图5.

 

package heap; public class Node { private int iData; // 结点数据是整型 public Node(int key) { iData = key; } public void setKey(int id) { iData = id; } public int getKey() { return iData; } }

 

package heap; public class MinHeap { private Node[] heapArray; // 堆容器 private int maxSize; // 堆得最大大小 private int currentSize; // 堆大小 public MinHeap(int _maxSize) { maxSize = _maxSize; heapArray = new Node[maxSize]; currentSize = 0; } /** * 自上而下调整 * * @param start * @param endOfHeap */ public void filterDown(int start, int endOfHeap) { int i = start; int j = 2 * i + 1; // j是i的左子女位置 Node temp = heapArray[i]; while (j <= endOfHeap) { // 检查是否到最后位置 if (j < endOfHeap // 让j指向两子女中的小者 && heapArray[j].getKey() > heapArray[j + 1].getKey()) { j++; } if (temp.getKey() <= heapArray[j].getKey()) { // 小则不做调整 break; } else { // 否则小者上移，i，j下降 heapArray[i] = heapArray[j]; i = j; j = 2 * j + 1; } } heapArray[i] = temp; } /** * 自下而上的调整:从结点start开始到0为止，自下向上比较，如果子女的值小于双亲结点的值则互相交换 * * @param start */ public void filterUp(int start) { int j = start; int i = (j - 1) / 2; Node temp = heapArray[j]; while (j > 0) { // 沿双亲结点路径向上直达根节点 if (heapArray[i].getKey() <= temp.getKey()) {// 双亲结点值小，不调整 break; } else {// 双亲结点值大，调整 heapArray[j] = heapArray[i]; j = i; i = (i - 1) / 2; } heapArray[j] = temp; // 回送 } } /** * 堆中插入结点 * * @param key * @return * @throws MinHeapException */ public boolean insert(int key) throws MinHeapException { boolean bool = true; if (isFull()) { bool = false; throw new MinHeapException("MinHeap is full!"); } else { Node newNode = new Node(key); heapArray[currentSize] = newNode; filterUp(currentSize); currentSize++; } return bool; } /** * 删除堆中的最小值 * * @return * @throws MinHeapException */ public Node removeMin() throws MinHeapException { if (isEmpty()) { throw new MinHeapException("MinHeap is empty!"); } Node root = heapArray[0]; heapArray[0] = heapArray[currentSize - 1]; currentSize--; filterDown(0, currentSize - 1); return root; } /** * 按某种格式输出堆 */ public void displayHeap() { System.out.print("heapArray: "); for (int i = 0; i < currentSize; i++) { if (heapArray[i] != null) { System.out.print(heapArray[i].getKey() + " "); } else { System.out.print("-- "); } } System.out.println(); int nBlanks = 32; // heap format int itemsPerRow = 1; int column = 0; int j = 0; // current item String dots = "..............................."; System.out.println(dots + dots); // dotted top line while (currentSize > 0) { // for each heap item if (column == 0) { // first item in row for (int k = 0; k < nBlanks; k++) { // preceding blanks System.out.print(" "); } } System.out.print(heapArray[j].getKey()); // display item if (++j == currentSize) { // done? break; } if (++column == itemsPerRow) { // end of row? nBlanks /= 2; // half the blanks itemsPerRow *= 2; // twice the items column = 0; // start over on System.out.println(); // next row } else { // next item on row for (int k = 0; k < nBlanks * 2 - 2; k++) { System.out.print(' '); // interim blanks } } } System.out.println("\n" + dots + dots); } public boolean isEmpty() { return currentSize == 0; } public boolean isFull() { return currentSize == maxSize; } public void makeEmpty() { currentSize = 0; } }

 

package heap; public class MinHeapException extends Exception { public MinHeapException() { super("MinHeapException"); } public MinHeapException(String exMsg) { super(exMsg); } }

 

package heap; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class MinHeapApp { /** * @param args * @throws IOException * @throws MinHeapException */ public static void main(String[] args) throws IOException, MinHeapException { int value, value2; MinHeap hp = new MinHeap(31); boolean success; hp.insert(53); hp.insert(17); hp.insert(78); hp.insert(9); hp.insert(45); hp.insert(65); hp.insert(87); hp.insert(23); while (true) { System.out.print("Enter first letter of "); System.out.print("show, insert, remove: "); int choice = getChar(); switch (choice) { case 's': hp.displayHeap(); break; case 'i': System.out.print("Enter value to insert: "); value = getInt(); success = hp.insert(value); if (!success) { System.out.println("Can't insert; heap is full"); } break; case 'r': if (!hp.isEmpty()) { hp.removeMin(); } else { System.out.println("Can't remove; heap is empty"); } break; default: System.out.println("Invalid entry\n"); } } } /** * 获得控制台输入流 * * @return * @throws IOException */ public static String getString() throws IOException { return new BufferedReader(new InputStreamReader(System.in)).readLine(); } /** * 获得控制台输入字符 * * @return * @throws IOException */ public static char getChar() throws IOException { return getString().charAt(0); } /** * 获得控制台输入整型 * * @return * @throws NumberFormatException * @throws IOException */ public static int getInt() throws NumberFormatException, IOException { return Integer.parseInt(getString()); } }