当前位置:网站首页>手写大根堆
手写大根堆
2022-08-09 12:01:00 【爱敲代码的Harrison】
用数组实现一个大根堆
实现功能
- 每给一个数加进数组后,自动调整为大根堆结构(heapInsert()方法)
- 返回大根堆中的最大值,并且在大根堆中把最大值删除,且剩下的数,依然保持为大根堆结构(heapify()方法)
自己手写一个大根堆结构 VS 纯暴力的方法,用对数器测试100万组!!!
package com.harrison.class04;
public class Code01_MaxHeap {
public static class MyMaxHeap {
private int[] heap;
private final int limit;
private int heapSize;
public MyMaxHeap(int limit) {
heap = new int[limit];
heapSize = 0;
this.limit = limit;
}
public void push(int value) {
if (heapSize == limit) {
throw new RuntimeException("heap is full");
}
heap[heapSize] = value;
heapInsert(heap, heapSize++);
}
// 堆结构的两个关键操作:从某个位置开始往上看
// 动态地建立大根堆
// 如果收了N个数,时间复杂度为logN
public static void heapInsert(int[] arr, int index) {
while (arr[index] > arr[(index - 1) / 2]) {
swap(arr, index, (index - 1) / 2);
index = (index - 1) / 2;
}
}
// 返回最大值,并在大根堆中把最大值删掉
// 剩下的数,依然保持大根堆组织
public int pop() {
int ans = heap[0];
swap(heap, 0, --heapSize);
heapify(heap, 0, heapSize);
return ans;
}
// 堆结构的两个关键操作:从某个位置开始往下调,时间复杂度logN
// heapSize 自己想象范围的大小,并不是数组的实际大小!!!
public static void heapify(int[] arr, int index, int heapSize) {
int left=(2*index)+1;
while(left<heapSize) {
int largest=(left+1<heapSize && arr[left+1]>arr[left])?left+1:left;
int allLargest=arr[largest]>arr[index]?largest:index;
if(allLargest==index) {
break;
}
swap(arr, allLargest, index);
index=allLargest;
left=(2*index)+1;
}
}
public boolean isEmpty() {
return heapSize==0;
}
public boolean isFull() {
return heapSize==limit;
}
}
public static void swap(int[] arr, int i, int j) {
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
public static class RightMaxHeap{
private int[] arr;
private int size;
private final int limit;
public RightMaxHeap(int limit) {
this.limit=limit;
arr=new int[limit];
size=0;
}
public void push(int value) {
if(size==limit) {
throw new RuntimeException("heap is full");
}
arr[size++]=value;
}
public int pop() {
int maxIndex=0;
for(int i=1; i<size; i++) {
if(arr[maxIndex]<arr[i]) {
maxIndex=i;
}
}
int ans=arr[maxIndex];
arr[maxIndex]=arr[--size];
return ans;
}
public boolean isEmpty() {
return size==0;
}
public boolean isFull() {
return size==limit;
}
}
public static void main(String[] args) {
int testTimes=1000000;
int limit=1000;
int value=100;
System.out.println("test begin");
for(int i=0; i<testTimes; i++) {
// [1,1000],防止出现零,否则一开始堆的大小就为0
int curLimit=(int)(Math.random()*limit)+1;
MyMaxHeap my=new MyMaxHeap(curLimit);
RightMaxHeap test=new RightMaxHeap(curLimit);
int curOopsTimes=(int)(Math.random()*limit);
for(int j=0; j<curOopsTimes; j++) {
if(my.isEmpty()!=test.isEmpty()) {
System.out.println("Oops");
}
if(my.isFull()!=test.isFull()) {
System.out.println("Oops");
}
if(my.isEmpty()) {
int curValue=(int)(Math.random()*(value+1));
my.push(curValue);
test.push(curValue);
}else if(my.isFull()) {
if(my.pop()!=test.pop()) {
System.out.println("Oops");
}
}else {
if(Math.random()<0.5) {
int curValue=(int)(Math.random()*(value+1));
my.push(curValue);
test.push(curValue);
}else {
if(my.pop()!=test.pop()) {
System.out.println("Oops");
}
}
}
}
}
System.out.println("finish");
}
}
边栏推荐
- 用皮肤“听”音乐,网友戴上这款装备听音乐会:仿佛住在钢琴里
- 问题来了:4GB物理内存的机器上申请8G内存能成功吗?
- Blazor Server (9) from scratch -- modify Layout
- 告别手摇织布机的AI时代
- WPF 实现带蒙版的 MessageBox 消息提示框
- AI篮球裁判火了,走步算得特别准,就问哈登慌不慌
- Too much volume... Tencent was asked on the side that the memory was full, what would happen?
- 我们真的需要DApp吗?App真的不能满足我们的幻想吗?
- 放下手机吧:实验表明花20分钟思考和上网冲浪同样快乐
- 十分钟教会你如何使用VitePress搭建及部署个人博客站点
猜你喜欢
Batch大小不一定是2的n次幂!ML资深学者最新结论
非科班AI小哥火了:他没有ML学位,却拿到DeepMind的offer
读写分离后,性能居然提升100%了呀
HAproxy:负载均衡
腾讯欲成育碧最大股东/ 米哈游招NLP内容生成研究员/ AI发现四千余物种濒临灭绝...今日更多新鲜事在此...
Too much volume... Tencent was asked on the side that the memory was full, what would happen?
【Untitled】
Programmer's Exclusive Romance - Use 3D Engine to Realize Fireworks in 5 Minutes
AQS同步组件-FutureTask解析和用例
阻塞、非阻塞、多路复用、同步、异步、BIO、NIO、AIO 一锅端
随机推荐
ARP协议原理
2022 Niu Ke Duo School (6) M. Z-Game on grid
Reading and writing after separation, performance were up 100%
Shell正则表达式,三剑客之grep命令
8、IDEA提交代码出现: Fetch failed fatal: Could not read from remote repository
Scala 高阶(七):集合内容汇总(上篇)
ABP 6.0.0-rc.1的新特性
水能自发变成“消毒水”,83岁斯坦福教授:揭示冬天容易得流感的部分原因...
一甲子,正青春,CCF创建六十周年庆典在苏州举行
Ways to prevent data fraud
00后写个暑假作业,被监控成这笔样
JD.com architects tidy up: what are the core technical knowledge points of jvm and performance tuning
用皮肤“听”音乐,网友戴上这款装备听音乐会:仿佛住在钢琴里
读写分离后,性能居然提升100%了呀
MySQL中的锁
Two ways to enter the Oracle database
数字化转型之支撑保障单元
推荐一个免费50时长的AI算力平台
荣耀携手Blue Yonder,加快企业战略增长
内网穿透工具ngrok使用教程