当前位置:网站首页>handwritten big pile
handwritten big pile
2022-08-09 13:43:00 【Love to knock code 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");
}
}
边栏推荐
- Yocto 可以下载的第三方库
- Glory to the Blue Yonder, speeds up the strategic growth
- ansible-cmdb友好展示ansible收集主机信息
- read stream 特别注意
- 安踏携手华为运动健康共同验证冠军跑鞋 创新引领中国体育
- 随机快排时间复杂度是N平方?
- About the handling of variable parameters in the Retrofit network request URL
- Flutter入门进阶之旅(十)Dialog&Toast
- 驻波比计算方法
- MySQL principle and optimization of Group By optimization techniques
猜你喜欢
第六届“强网杯”全国网络安全挑战赛
系统提供的堆 VS 手动改写堆
Win10 compiles the x264 library (there are also generated lib files)
Customize VIEW to realize in-app message reminder to rotate up and down
Resolved IndentationError: unindent does not match any oute r indentation Level
h264 protocol
26. Pipeline parameter substitution command xargs
World's 4th mad scientist dies on his 103rd birthday
用 API Factory 产品生成 API 文档
The batch size does not have to be a power of 2!The latest conclusions of senior ML scholars
随机推荐
Flutter Getting Started and Advanced Tour (2) Hello Flutter
流量焦虑背后是企业对客户关系管理的不足
ViewPager fragments of nested data blank page abnormal problem analysis
工作任务统计
WebView注入Js代码实现大图自适应屏幕点击图片预览详情
Rust from entry to proficient 04 - data types
技术分享 | 接口自动化测试如何处理 Header cookie
链表噩梦之一?5000多字带你弄清它的来龙去脉
telnet+ftp 对设备进行 操控 和 升级
手写大根堆
Adalvo acquires its first branded product, Onsolis
Scala Advanced (7): Collection Content Summary (Part 1)
Rust从入门到精通04-数据类型
十进制数字→十六进制字符
在“Extend the Omniverse”比赛中构建用于 3D 世界的工具
批量读取word docx文件指定表格内容,保存在excel文件中
Win10 compiles the x264 library (there are also generated lib files)
电脑重装系统还原0x80070005错误如何解决
Simple understanding of ThreadLocal
The FFmpeg library is configured and used on win10 (libx264 is not configured)