在上篇文章数据结构:堆《概念》中已经讲述什么堆,有什么特点。废话不多,直接上干货。今天实现堆中的大堆。
/**
* 大顶堆
*/
public class MaxHeap {
private int maxSize;
private int[] arrs;
//初始化堆
public MaxHeap(int n) {
arrs = new int[n];
maxSize = 0;
}
//大顶堆建堆
public void addMaxHeap(int i){
int size = this.maxSize;
if (size==0) {
arrs[0] = i;
} else {
while (size>0 && arrs[size/2]<i){
arrs[size] = arrs[size/2];
size = size/2;
}
arrs[size] = i;
}
this.maxSize++;
}
//大顶堆删除
public int deleteMaxHeap(){
if (this.maxSize==0) {
return -1;
}
int top = arrs[0];
int last = arrs[this.maxSize-1];
arrs[0] = last;
this.maxSize--;
//堆化
maxHeapify(0);
return top;
}
//大顶堆化
public void maxHeapify(int i){
int L = 2*i,R=2*i+1,max;
if (L<=maxSize && arrs[L] > arrs[i]) {
max = L;
} else {
max = i;
}
if (R <= maxSize && arrs[R] > arrs[max]) {
max = R;
}
if (max!=i){
int t = arrs[max];
arrs[max] = arrs[i];
arrs[i] = t;
maxHeapify(max);
}
}
//输出堆
public void print(){
for (int i = 0; i < this.maxSize; i++) {
System.out.print(arrs[i]+" ");
}
System.out.println();
}
public static void main(String[] args) {
int arrs [] = {1,3,6,4,8,7};
int n = arrs.length;
MaxHeap heapNode = new MaxHeap(n);
for (int i = 0; i < n; i++) {
heapNode.addMaxHeap(arrs[i]);
}
heapNode.print();
for (int i = 0; i < n; i++) {
int min = heapNode.deleteMaxHeap();
System.out.print("堆顶:"+min+" 剩下堆元素:");
heapNode.print();
}
}
}