数据结构之堆

1。概念：堆是一种特殊的二叉树，具备以下两种性质
1）每个节点的值都大于（或者都小于，称为最小堆）其子节点的值
2）树是完全平衡的，并且最后一层的树叶都在最左边
这样就定义了一个最大堆。

2。堆可以用一个数组表示，有如下性质：
heap[i]>=heap[2*i+1]  其中0<=i<=(n-1)/2
heap[i]>=heap[2*i+2]  其中0<=i<=(n-2)/2

3。用数组实现堆，
1）插入操作
自顶向下，伪代码：

  heapEnqueue(el)
      将el放在堆尾
      while el不在根节点并且el>parent(el)
          交换el及其父节点

自底向上，伪代码：

 FloydAlgrithm(data[])
     for i=最后一个非叶节点的下标,i>=0;i--
      调用moveDown(data,i,n-1)恢复以data[i]为根的树的堆性质


  
2)moveDown的方法实现，此方法是堆排序的关键，也是删除操作的关键。删除操作，将根节点删除，并把最末的树叶换到根节点，通过moveDown方法找到正确的位置，恢复堆性质。

4。堆的一个实现：

// 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;
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()
// -------------------------------------------------------------
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()
// -------------------------------------------------------------
public void trickleDown(int index)
{
int largerChild;
Node top = heapArray[index];       // save root
while(index < currentSize/2)       // while node has at
{                               //    least one child,
int leftChild = 2*index+1;
int rightChild = leftChild+1;
// find larger child
if(rightChild < currentSize &&  // (rightChild exists?)
heapArray[leftChild].getKey() <
heapArray[rightChild].getKey())
largerChild = rightChild;
else
largerChild = leftChild;
// top >= largerChild?
if( top.getKey() >= heapArray[largerChild].getKey() )
break;
// shift child up
heapArray[index] = heapArray[largerChild];
index = largerChild;            // go down
}  // end while
heapArray[index] = top;            // root to index
}  // end trickleDown()
// -------------------------------------------------------------
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;                          // 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(' ');
// 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 current 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
////////////////////////////////////////////////////////////////

文章转自庄周梦蝶  ，原文发布时间5.17