详解Java如何实现小顶堆和大顶堆详解Java如何实现小顶堆和大顶

大顶堆每个结点的值都大于或等于其左右孩子结点的值
小顶堆每个结点的值都小于或等于其左右孩子结点的值
对比图
文章图片

实现代码

public class HeapNode{private int size; //堆大小private int[] heap; //保存堆数组//初始化堆public HeapNode(int n) {heap = new int[n]; size = 0; }//小顶堆建堆public void minInsert(int key){int i = this.size; if (i==0) heap[0] = key; else {while (i>0 && heap[i/2]>key){heap[i] = heap[i/2]; i = i/2; }heap[i] = key; }this.size++; }//大顶堆建堆public void maxInsert(int key){int i = this.size; if (i==0) heap[0] = key; else {while (i>0 && heap[i/2] heap[i]) max = L; else max = i; if (R <= size && heap[R] > heap[max]) max = R; if (max!=i){int t = heap[max]; heap[max] = heap[i]; heap[i] = t; maxHeapify(max); }}//输出堆public void print(){for (int i = 0; i < this.size; i++) {System.out.print(heap[i]+" "); }System.out.println(); }}

测试

public class Heap {static int[] a = {5,3,6,4,2,1}; static int n = a.length; public static void main(String[] args){HeapNode heapNode = new HeapNode(n); for (int i = 0; i < n; i++) {heapNode.maxInsert(a[i]); }heapNode.print(); for (int i = 0; i < n; i++) {int min = heapNode.maxDelete(); System.out.print("堆顶："+min+" 剩下堆元素："); heapNode.print(); }}}

结果 【详解Java如何实现小顶堆和大顶堆】