堆

1 堆介绍

堆是一棵根最大（最小）的完全二叉树 本示例用数组存储一棵最大堆，Java语言实现

2 实现

/** * Java实现最大堆 * @author xld * */ public class MaxHeap { private int[] data; private int count; private int capacity; //构造函数 public MaxHeap(int capacity){ this.data=new int[capacity+1]; this.count=0; this.capacity=capacity; } //判断堆是否为空 public boolean isEmpty(){ return count==0; } //返回堆的长度 public int size(){ return count; } //添加数据 public void insert(int val){ assert count+1<capacity; data[count+1]=val; count++; shiftUp(count); } // 从最大堆中取出堆顶元素, 即堆中所存储的最大数据 public int extractMax(){ assert count>0; int ret = data[1]; swap(data,1,count); shiftDown(1); return ret; } // 获取最大堆中的堆顶元素 public int getMax(){ assert(count>0); return data[1]; } /** * 辅助函数 */ public void shiftUp(int k){ while(k>1 &&data[k]>data[k/2]){ swap(data,k,k/2); k/=2; } } public static void swap(int[] arr, int a, int b) { int temp = arr[a]; arr[a] = arr[b]; arr[b] = temp; } /** * 将元素向下移动 * @param k */ public void shiftDown(int k){ while(2*k<count){ int j=2*k; //在次轮循环中，交换data[k]和data[j]的位置 if(j+1<count && data[j+1]>data[j]) j++; //data[j]为k子节点的最大值 if(data[k]>data[j]) break; swap(data,k,j); k=j; } } public static void main(String[] args) { MaxHeap heap = new MaxHeap(10); for(int i=0;i<10;i++){ heap.insert(i+1); } System.out.println(heap.getMax()); } }