1 堆
1)堆中某个节点的值总是不大于或不小于其父节点的值;
2)堆总是一棵完全数。
将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。下面主要讨论二叉堆。
堆常用数组实现,如果父亲节点在数组中的位置是index,则其左节点位置是2*index+1,右节点位置是2*index+2.
堆为什么通常用数组实现?
To insert an element into a heap, you can place it anywhere and swap it with its parent until the heap constraint is valid again. Swap-with-parent is an operation that keeps the binary tree structure of the heap
intact. This means a heap of size N will be represented as an N-cell array, and you can add a new element in logarithmic time.
A binary search tree can be represented as an array of size N using the same representation structure as a heap (children 2n and 2n+1), but inserting an element this way is a lot harder, because unlike the heap
constraint, the binary search tree constraint requires rotations to be performed to retrieve a balanced tree. So, either you do manage to keep an N-node tree in an N-cell array at a cost higher than logarithmic, or you waste space by keeping the tree in a
larger array (if my memory serves, a red-back tree could waste as much as 50% of your array).
So, a binary search tree in an array is only interesting if the data inside is constant. And if it is, then you don't need the heap structure (children 2n and 2n+1) : you can just sort your array and use binary
search.
堆的伪代码如下:
class Heap { private Node heapArray[]; public void insert(Node nd) {... } public Node remove() {... } public Node getRoot() {...} }
2 堆的应用
2.1 优先队列
class priorityQueue { private Heap theHeap; public void insert(Node nd) { theHeap.insert(nd); } public Node remove() { return theHeap.remove() } public Node getM() //获取最大值或最小值 { return theHeap.getRoot()}
2.2 堆排序
堆排序通过在同一个数组中交叉两个抽象结构(堆和数列),从而避免了使用而外的空间。
虽然堆排序保证了最差情况下仍具有O(nlogn)性能,但对于典型的输入数据,最快的堆排序通常也比快速排序慢。
将堆的root节点取出,此时数组最后一个元素为空,将root节点移至数组尾部。
重复此步骤,直到堆中没有元素
public heapSort(){ for(j=size-1; j>=0; j--) // remove from heap and store at array end { Node rootNode = theHeap.remove(); heapArray[j]=rootNode; } System.out.print(“Sorted: “); theHeap.displayArray(); // display sorted array--heapArray }
3 堆代码实现
在堆中删除元素
在堆中添加元素
// heap.java // demonstrates heaps // to run this program: C>java HeapApp import java.io.*; //////////////////////////////////////////////////////////////// class Node { private int iData; // data item (key) // ------------------------------------------------------------- public Node(int key) // constructor { iData = key; } // ------------------------------------------------------------- public int getKey() { return iData; } // ------------------------------------------------------------- public void setKey(int id) { iData = id; } // ------------------------------------------------------------- } // end class Node //////////////////////////////////////////////////////////////// class Heap { private Node[] heapArray; //heap is implemented as an array private int maxSize; // size of array private int currentSize; // number of nodes in array // ------------------------------------------------------------- public Heap(int mx) // constructor { maxSize = mx; currentSize = 0; heapArray = new Node[maxSize]; // create array } // ------------------------------------------------------------- public boolean isEmpty() { return currentSize==0; } // ------------------------------------------------------------- /* */ public boolean insert(int key) { if(currentSize==maxSize) return false; Node newNode = new Node(key); heapArray[currentSize] = newNode; trickleUp(currentSize++); return true; } // end insert() // ------------------------------------------------------------- public void trickleUp(int index) { int parent = (index-1) / 2; Node bottom = heapArray[index]; while( index > 0 && heapArray[parent].getKey() < bottom.getKey() ) { heapArray[index] = heapArray[parent]; // move it down index = parent; parent = (parent-1) / 2; } // end while heapArray[index] = bottom; } // end trickleUp() // ------------------------------------------------------------- /* step1:sepecial case heap is null, or heap has only one node step2: remove the root step3: move the last node into the root step3: trickle down Trickle the last node down until it’s below a larger node and above a smaller one. base case :top>=largerChild(leftChild,rightChild) */ public Node remove() // delete item with max key { // (assumes non-empty list) Node root = heapArray[0]; heapArray[0] = heapArray[--currentSize]; trickleDown(0); return root; } // end remove() // ------------------------------------------------------------- /* step1: special case index is out of bound of array step2: initial top node, its leftChild ,rightChild int leftChild=2*index+1; int rightChild=2*index+2; step3: have no child leftChild> top-1 step4: get larger child 1)have on child leftChild<=top-1 && rightChild>currentSize-1 2) have two children step5: compare top with larger child if top>=larger child, break */ public void tricleDown(int index){ int largerChild; Node top=heapArray[index]; //save root int leftChild=2*index+1; int rightChild=2*index+2; //have no child if(leftChild> top-1) return; while(true){ //get the largerChild //have only left child if(rightChild>currentSize-1) larteChild=leftChild; else{ //have two children if(heapArray[leftChild].getKey() < heapArray[rightChild].getKey()) largerChild=rightChild; else largerChild=leftChild; }//end else // top >= largerChild if( top.getKey() >= heapArray[largerChild].getKey() ) //base case break; // shift child up heapArray[index] = heapArray[largerChild]; index = largerChild; // go down }//end while }// tricleDown() // ------------------------------------------------------------- public boolean change(int index, int newValue) { if(index<0 || index>=currentSize) return false; int oldValue = heapArray[index].getKey(); // remember old heapArray[index].setKey(newValue); // change to new if(oldValue < newValue) // if raised, trickleUp(index); // trickle it up else // if lowered, trickleDown(index); // trickle it down return true; } // end change() // ------------------------------------------------------------- public void displayHeap() { System.out.print("heapArray: "); // array format for(int m=0; m<currentSize; m++) if(heapArray[m] != null) System.out.print( heapArray[m].getKey() + " "); else System.out.print( "-- "); System.out.println(); // heap format int nBlanks = 32; int itemsPerRow = 1; int column = 0; int j = 0; // top 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(' '); // display item System.out.print(heapArray[j].getKey()); 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(); // new row } else // next item on row for(int k=0; k<nBlanks*2-2; k++) System.out.print(' '); // interim blanks } // end for System.out.println("\n"+dots+dots); // dotted bottom line } // end displayHeap() // ------------------------------------------------------------- } // end class Heap //////////////////////////////////////////////////////////////// class HeapApp { public static void main(String[] args) throws IOException { int value, value2; Heap theHeap = new Heap(31); // make a Heap; max size 31 boolean success; theHeap.insert(70); // insert 10 items theHeap.insert(40); theHeap.insert(50); theHeap.insert(20); theHeap.insert(60); theHeap.insert(100); theHeap.insert(80); theHeap.insert(30); theHeap.insert(10); theHeap.insert(90); while(true) // until [Ctrl]-[C] { System.out.print("Enter first letter of "); System.out.print("show, insert, remove, change: "); int choice = getChar(); switch(choice) { case 's': // show theHeap.displayHeap(); break; case 'i': // insert System.out.print("Enter value to insert: "); value = getInt(); success = theHeap.insert(value); if( !success ) System.out.println("Can't insert; heap full"); break; case 'r': // remove if( !theHeap.isEmpty() ) theHeap.remove(); else System.out.println("Can't remove; heap empty"); break; case 'c': // change System.out.print("Enter top index of item: "); value = getInt(); System.out.print("Enter new key: "); value2 = getInt(); success = theHeap.change(value, value2); if( !success ) System.out.println("Invalid index"); break; default: System.out.println("Invalid entry\n"); } // end switch } // end while } // end main() //------------------------------------------------------------- public static String getString() throws IOException { InputStreamReader isr = new InputStreamReader(System.in); BufferedReader br = new BufferedReader(isr); String s = br.readLine(); return s; } //------------------------------------------------------------- public static char getChar() throws IOException { String s = getString(); return s.charAt(0); } //------------------------------------------------------------- public static int getInt() throws IOException { String s = getString(); return Integer.parseInt(s); } //------------------------------------------------------------- } // end class HeapApp ////////////////////////////////////////////////////////////////
4 堆排序算法效率
时间复杂度O(NlogN)
空间复杂度O(1)