您好,登录后才能下订单哦!
密码登录
登录注册
点击 登录注册 即表示同意《亿速云用户服务条款》
本篇内容主要讲解“如何用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]<key){ heap[i] = heap[i/2]; i = i/2; } heap[i] = key; } this.size++; } //小顶堆删除 public int minDelete(){ if (this.size==0) return -1; int top = heap[0]; int last = heap[this.size-1]; heap[0] = last; this.size--; //堆化 minHeapify(0); return top; } //大顶堆删除 public int maxDelete(){ if (this.size==0) return -1; int top = heap[0]; int last = heap[this.size-1]; heap[0] = last; this.size--; //堆化 maxHeapify(0); return top; } //小顶堆化 public void minHeapify(int i){ int L = 2*i,R=2*i+1,min; if (L<=size && heap[L] < heap[i]) min = L; else min = i; if (R <= size && heap[R] < heap[min]) min = R; if (min!=i){ int t = heap[min]; heap[min] = heap[i]; heap[i] = t; minHeapify(min); } } //大顶堆化 public void maxHeapify(int i){ int L = 2*i,R=2*i+1,max; if (L<=size && heap[L] > 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实现小顶堆和大顶堆”有了更深的了解,不妨来实际操作一番吧!这里是亿速云网站,更多相关内容可以进入相关频道进行查询,关注我们,继续学习!
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。