·它是完全二叉樹。即除了樹的最後一層節點不需要是滿的外，其他的每一層從左到右都完全是滿的。
·它常常用一個數組實作。用數組實作的完全二叉樹中，節點的索引有如下特點（設該節點的索引為x）：
它的父節點的索引為 (x-1) / 2；
它的左子節點索引為 2*x + 1；
它的右子節點索引為 2*x + 2。
·堆中每個節點的關鍵字都大于（或等于）這個節點的子節點的關鍵字。這也是堆中每個節點必須滿足的條件。是以堆和二叉搜尋樹相比，是弱序的。
向堆中插入資料，首先将資料項存放到葉節點中（即存到數組的最後一項），然後從該節點開始，逐級向上調整，直到滿足堆中節點關鍵字的條件為止。
從堆中删除資料與插入不同，删除時永遠删除根節點的資料，因為根節點的資料最大，删除完後，将最後一個葉節點移到根的位置，然後從根開始，逐級向下調整，直到滿足堆中節點關鍵字的條件為止。具體的看下面的代碼：
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) {
int oldvalue = heaparray[index].getkey();
heaparray[index].setkey(newvalue);
if(oldvalue < newvalue) {
trickleup(index);
else {
trickledown(index);
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() + " ");
system.out.print("--");
}
class node {
private int idata;
public node(int key) {
idata = key;
public int getkey() {
return idata;
public void setkey(int key) {
堆就讨論到這裡，如有錯誤，歡迎留言指正~
轉載：http://blog.csdn.net/eson_15/article/details/51105955