Python 官方文档:入门教程 => 点击学习
大顶堆 每个结点的值都大于或等于其左右孩子结点的值 小顶堆 每个结点的值都小于或等于其左右孩子结点的值 对比图 实现代码 public class Heapnode{
每个结点的值都大于或等于其左右孩子结点的值
每个结点的值都小于或等于其左右孩子结点的值
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如何实现小顶堆和大顶堆的文章就介绍到这了,更多相关Java实现小顶堆和大顶堆内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网!
--结束END--
本文标题: 详解Java如何实现小顶堆和大顶堆
本文链接: https://www.lsjlt.com/news/128643.html(转载时请注明来源链接)
有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
下载Word文档到电脑,方便收藏和打印~
2024-03-01
2024-03-01
2024-03-01
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
回答
回答
回答
回答
回答
回答
回答
回答
回答
回答
0