当前位置： 首页 > article >正文

数据结构基础之《（11）—堆》

article 2025/2/1 22:53:14

一、堆结构

1、堆在结构上是一颗完全二叉树

2、大根堆和小根堆
大根堆：其特点在于每个节点的值都大于或等于其子节点的值
小根堆：其每个非叶子节点的值都小于或等于其子节点的值

3、树调整的代价logN

4、调整后为什么还是大根堆
若原堆是大根堆，最后一个数它肯定是整个堆里最小的数
假设它是最小的数，将它挪到顶，就必然要对每棵子树的头结点进行判断

5、自己实现堆结构代码

package class04;

public class Code02_Heap01 {

	public static class MyMaxHeap {
		private int[] heap; //一个数组作为堆
		private final int limit;
		private int heapSize;
		
		public MyMaxHeap(int limit) {
			heap = new int[limit];
			this.limit = limit;
			heapSize = 0;
		}
		
		public boolean isEmpty() {
			return heapSize == 0;
		}
		
		public boolean isFull() {
			return heapSize == limit;
		}
		
		public void push(int value) {
			if (heapSize == limit) { //heapSize到极限了
				throw new RuntimeException("heap is full");
			}
			heap[heapSize] = value; //value放在heapSize位置
			heapInsert(heap, heapSize++);
		}
		
		/**
		 * 用户获取最大值，返回最大值并且在大根堆中把最大值删掉
		 * 剩下的数，依然保持大根堆组织
		 * @return
		 */
		public int pop() {
			int ans = heap[0]; //返回0位置的数
			swap(heap, 0, --heapSize); //把最后一个位置的值和0位置的值交换
			heapify(heap, 0, heapSize); //从0位置开始，做heapify
			return ans;
		}
		
		public void heapInsert(int[] arr, int index) {
			// arr[index]是新进来的数
			// 停止条件：
			// （1）arr[index]不比arr[index父]大了，停
			// （2）当heapSize=0，arr[(index - 1) / 2]是它自己，停
			while (arr[index] > arr[(index - 1) / 2]) { //比较arr[index]节点值和它的父亲节点的值
				swap(arr, index, (index - 1) / 2); //交换
				index = (index - 1) / 2; //然后index来到它父亲节点的位置
			}
		}
		
		/**
		 * 从index位置往下看，树不断的下沉
		 * 停止条件：我的孩子都不再比我大，或者已经没有孩子了
		 * @param arr
		 * @param index
		 * @param heapSize
		 */
		private void heapify(int[] arr, int index, int heapSize) {
			int left = index * 2 + 1; //左孩子的下标
			while (left < heapSize) { //左孩子没越界
				// 左右两个孩子中，谁大，谁把自己的下标给largest
				int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
				// 判断值有没有父节点大
				largest = arr[largest] > arr[index] ? largest : index;
				// 说明左右孩子都没有index大
				if (largest == index) {
					break;
				}
				swap(arr, largest, index);
				index = largest; //index位置往下沉
				left = index * 2 + 1; //继续找下一步的左孩子
			}
		}
		
		private void swap(int[] arr, int i, int j) {
			int tmp = arr[i];
			arr[i] = arr[j];
			arr[j] = tmp;
		}
	}
	
	/**
	 * 绝对对的大根堆
	 * 用来比较
	 */
	public static class RightMaxHeap {
		private int[] arr;
		private final int limit;
		private int size;
		
		public RightMaxHeap(int limit) {
			arr = new int[limit];
			this.limit = limit;
			size = 0;
		}
		
		public boolean isEmpty() {
			return size == 0;
		}
		
		public boolean isFull() {
			return size == limit;
		}
		
		//加的时候直接加在最后面
		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 = 0; i < size; i++) {
				if (arr[i] > arr[maxIndex]) {
					maxIndex = i;
				}
			}
			int ans = arr[maxIndex];
			arr[maxIndex] = arr[--size];
			return ans;
		}
	}
	
	public static void main(String[] args) {
		int value = 1000;
		int limit = 100;
		int testTimes = 1000000; //测试100万次，随机的次数加入和弹出
		for (int i = 0; i < testTimes; i++) {
			int curLimit = (int) (Math.random() * limit) + 1;
			MyMaxHeap my = new MyMaxHeap(curLimit);
			RightMaxHeap test = new RightMaxHeap(curLimit);
			int curOpTimes = (int) (Math.random() * limit);
			for (int j = 0; j < curOpTimes; 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);
					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) { //以0.5的概率加入
						int curValue = (int) (Math.random() * value);
						my.push(curValue);
						test.push(curValue);
					} else { //以剩下0.5的概率弹出
						if (my.pop() != test.pop()) {
							System.out.println("Oops!");
						}
					}
				}
			}
		}
		System.out.println("finish!");
	}
	
}

二、堆排序

1、用户给你一串数，是无序的
思路：
（1）先将这串数，变为大根堆，即第一步
（2）在利用叶子下沉完成从小到大排序

2、代码

package class04;

public class Code04_HeapSort {

	public static void heapSort(int[] arr) {
		if (arr == null || arr.length < 2) {
			return;
		}
		
		System.out.println("step1...start");
		
		// 经典堆排序
		// 第一步
		// 总体是O(N*logN)
		for (int i = 0; i < arr.length; i++) { //这一步是O(N)
			heapInsert(arr, i); //这一步是O(logN)
		}
		
		// 这是上面堆排序的优化
//		for (int i = arr.length - 1; i >= 0; i--) {
//			heapify(arr, i, arr.length);
//		}
		
		System.out.println("step1...end");
		
		int heapSize = arr.length;
		swap(arr, 0, --heapSize);
		
		for (int i : arr) {
			System.out.print(i + " ");
		}
		System.out.println();
		
		System.out.println("step2...start");
		
		// 第二步
		// 总体是O(N*logN)
		while(heapSize > 0) { //这一步是O(N)
			heapify(arr, 0, heapSize); //这一步是O(logN)
			swap(arr, 0, --heapSize); //这一步是O(1)
			
			for (int i : arr) {
				System.out.print(i + " ");
			}
			System.out.println();
		}
		
		System.out.println("step2...end");
	}
	
	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;
			
			for (int i : arr) {
				System.out.print(i + " ");
			}
			System.out.println();
			
		}
	}
	
	/**
	 * 从index位置往下看，树不断的下沉
	 * 停止条件：我的孩子都不再比我大，或者已经没有孩子了
	 * @param arr
	 * @param index
	 * @param heapSize
	 */
	public static void heapify(int[] arr, int index, int heapSize) {
		int left = index * 2 + 1; //左孩子的下标
		while (left < heapSize) { //左孩子没越界
			// 左右两个孩子中，谁大，谁把自己的下标给largest
			int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
			// 判断值有没有父节点大
			largest = arr[largest] > arr[index] ? largest : index;
			// 说明左右孩子都没有index大
			if (largest == index) {
				break;
			}
			swap(arr, largest, index);
			index = largest; //index位置往下沉
			left = index * 2 + 1; //继续找下一步的左孩子
		}
	}
	
	public static void swap(int[] arr, int i, int j) {
		int tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;
	}
	
	public static void main(String[] args) {
		int[] arr = {6, 5, 3, 2, 1, 0, 9};
		heapSort(arr);
		
		for (int i : arr) {
			System.out.print(i + " ");
		}
		System.out.println();
		
	}
}

执行结果：

step1...start
6 5 9 2 1 0 3 
9 5 6 2 1 0 3 
step1...end
3 5 6 2 1 0 9 
step2...start
0 5 3 2 1 6 9 
1 2 3 0 5 6 9 
0 2 1 3 5 6 9 
1 0 2 3 5 6 9 
0 1 2 3 5 6 9 
0 1 2 3 5 6 9 
step2...end
0 1 2 3 5 6 9


http://www.kler.cn/a/427905.html

相关文章：

  • 使用 Tauri 2 + Next.js 开发跨平台桌面应用实践：Singbox GUI 实践
  • SpringCloudGateWay和Sentinel结合做黑白名单来源控制
  • 音视频多媒体编解码器基础-codec
  • 【线上问题定位处理】及【性能优化】系列文章
  • 【自学嵌入式（7）天气时钟：WiFi模块、OLED模块、NTP模块开发】
  • 爬虫基础（三）Session和Cookie讲解
  • 【3D AIGC】Img-to-3D、Text-to-3D、稀疏重建（2024年文章汇总）
  • 【技术支持】关于html中移动端innerwidth的问题
  • 『MySQL 实战 45 讲』24 - MySQL是怎么保证主备一致的？
  • C++学习-类+对象+函数
  • 【oracle数据库提示oracle initialization or shutdown in process】
  • Spring完整知识点二
  • 17. Threejs案例-Three.js创建多个立方体
  • burpsuite（6）暴力破解与验证码识别绕过
  • ansible基础教程（上）
  • UE5 Compile Plugins | Rebuild from Source Manually | Unreal Engine | Tutorial
  • 如何在Ubuntu 20.04上编译安装OpenCV 4.4并启用pkg-config支持
  • 【工具变量】上市公司企业商业信用融资数据（2003-2022年）
  • LeetCode - #152 乘积最大子数组（Top 100）
  • ADB常用各模块操作命令
  • 第二部分：基础知识 5.控制流 --[JavaScript 新手村：开启编程之旅的第一步]
  • 【趋势红蓝交易】主图指标操盘技术图文展示，注意要点，通达信炒股软件指标
  • Android 按两下power键不打开相机改为打开手电筒
  • 第三周作业
  • 如何在MySQL中开启死锁日志及查看日志
  • 超详细！！关于Docker的访问仓库操作