<span style="font-size:32px;">package com.liebao34;
public class Heap {
private Node[] heapArr;
private int maxSize;
private int currentSize;
public Heap(int mx){
maxSize = mx;
currentSize = 0;
heapArr = new Node[maxSize];
}
public boolean isEmpty(){
return currentSize==0;
}
public boolean insert(int key){
if(currentSize==maxSize)
return false;
Node newNode = new Node(key);
heapArr[currentSize] = newNode;
trickleUp(currentSize);
currentSize++;
return true;
}
public void trickleUp(int index){
int parent = (index-1)/2;
Node bottom = heapArr[index];
while(index>0 && heapArr[parent].getKey()<bottom.getKey()){
heapArr[index] = heapArr[parent];
index = parent;
parent = (parent-1)/2;
}
heapArr[index] = bottom;
}
public Node remove(){
Node root = heapArr[0];
heapArr[0] = heapArr[--currentSize];
trickleDown(0);
return root;
}
public void trickleDown(int index){
int largeChild;
Node top = heapArr[index];
while(index<currentSize/2){
int leftChild = 2*index+1;
int rightChild = leftChild+1;
if(rightChild<currentSize&&heapArr[leftChild].getKey()<heapArr[rightChild].getKey()){
largeChild = rightChild;
}else{
largeChild = leftChild;
}
if(top.getKey()>=heapArr[largeChild].getKey())break;//no need to exchange
heapArr[index]=heapArr[largeChild];
index = largeChild;
}
heapArr[index] = top;
}
public boolean change(int index,int newValue){
if(index<0||index>=currentSize){
return false;
}
int oldValue = heapArr[index].getKey();
heapArr[index].setKey(newValue);
if(oldValue<newValue){
trickleUp(index);
}else{
trickleDown(index);
}
return true;
}
public void displayHeap(){
System.out.println("HeapArray: ");
for(int i=0;i<currentSize;i++){
if(heapArr[i]!=null){
System.out.print(heapArr[i].getKey()+" ");
}else {
System.out.print("-- ");
}
}
System.out.println();
//display by tree
int nBlanks = 32;
int itemPerRow = 1;
int column = 0;
int j=0;
String dot = "............";
System.out.println(dot+dot);
while (currentSize>0) {
if(column==0){
for(int k =0;k<nBlanks;k++){
System.out.print(" ");
}
}
System.out.print(heapArr[j].getKey());
if(++j==currentSize)break;
if(++column==itemPerRow){
nBlanks/=2;
itemPerRow*=2;
column=0;
System.out.println();
}else{
for(int k=0;k<nBlanks*2-2;k++){
System.out.print(" ");
}
}
}
System.out.println("\n"+dot+dot);
}
}
</span>
<span style="font-size:32px;">
</span>
<pre name="code" class="java"><span style="font-size:32px;">package com.liebao34;
public class Node {
private int iData;
public Node(int key){
iData = key;
}
public int getKey(){
return iData;
}
public void setKey(int id){
iData = id;
}
}
</span>
<pre name="code" class="java"><span style="font-size:32px;">package com.liebao34;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class HeapApp {
public static void main(String[] args) throws Exception{
int value,value2;
Heap theHeap = new Heap(31);
boolean success ;
theHeap.insert(70);
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){
System.out.print("Enter first letter: show,change,insert,remove,change:");
char choice = getChar();
switch (choice) {
case 's':
theHeap.displayHeap();
break;
case 'i':
System.out.print("Enter value to insert: ");
value = getInt();
success = theHeap.insert(value);
if(!success){
System.out.print("Cna not insert,heap is full!");
}
break;
case 'r':
if(!theHeap.isEmpty()){
theHeap.remove();
}else{
System.out.println("can not remove,heap is empty");
}
break;
case 'c':
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 input!\n");
}
}
}
public static String getString() throws IOException{
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(isr);
return br.readLine();
}
public static char getChar() throws IOException{
return getString().charAt(0);
}
public static int getInt() throws IOException{
return Integer.parseInt(getString());
}
}</span>
输出:
<pre name="code" class="java"><span style="font-size:32px;">Enter first letter: show,change,insert,remove,change:s
HeapArray:
100 90 80 30 60 50 70 20 10 40
........................
100
90 80
30 60 50 70
20 10 40
........................
Enter first letter: show,change,insert,remove,change:i
Enter value to insert: 77
Enter first letter: show,change,insert,remove,change:i
Enter value to insert: 120
Enter first letter: show,change,insert,remove,change:s
HeapArray:
120 90 100 30 77 80 70 20 10 40 60 50
........................
120
90 100
30 77 80 70
20 10 40 60 50
........................
Enter first letter: show,change,insert,remove,change:c
Enter current index of item.3
Enter new key: 33
Enter first letter: show,change,insert,remove,change:s
HeapArray:
120 90 100 33 77 80 70 20 10 40 60 50
........................
120
90 100
33 77 80 70
20 10 40 60 50
........................
Enter first letter: show,change,insert,remove,change:c
Enter current index of item.3
Enter new key: 130
Enter first letter: show,change,insert,remove,change:s
HeapArray:
130 120 100 90 77 80 70 20 10 40 60 50
........................
130
120 100
90 77 80 70
20 10 40 60 50
........................
Enter first letter: show,change,insert,remove,change:</span>
堆的特点:
<span style="font-size:32px;">1.它是一种完全二叉树,除了树的最后一个节点不需要是满的,其他的每一层从左到右都完全是满的;</span>
<span style="font-size:32px;">2.它常常使用数组实现的;</span>
<span style="font-size:32px;">3.堆中的每个节点都满足堆的条件,父亲节点的关键字要大于子节点;</span>
<span style="font-size:32px;">4.堆是弱序的.</span>