堆及其java手写实现

2024-06-22 22:20

文章标签 java 实现手写

本文主要是介绍堆及其java手写实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

堆（Heap）是计算机科学中一种常用且高效的数据结构，通常被实现为一个完全二叉树。这个树形结构中的每个节点都有一个关联的值，并且这个值遵循一定的规则，从而使得堆具备特殊的性质，主要分为两种类型：大顶堆和小顶堆。

基本概念：

完全二叉树：这是一种特殊的二叉树，除了最后一层外，每一层都被完全填满，最后一层的节点都尽可能地靠左排列。
数组表示：由于完全二叉树的特性，堆常通过数组来紧凑存储，其中数组的索引关系反映了节点间的父子关系。例如，在数组中，索引i的节点的父节点是索引i/2（向下取整），而其左、右孩子分别是索引2i和2i+1。

堆的性质：

大顶堆：在每个节点上，父节点的值总是大于或等于其孩子的值。因此，堆的根节点是整个堆中的最大值。
小顶堆：与大顶堆相反，每个节点的值总是小于或等于其孩子的值，使得堆的根节点是整个堆中的最小值。

1 代码实现

package org.example.code;/*** @author Mazai-Liu* @time 2024/6/22*/
public class MyHeap {private int[] heapArray;private int heapSize;public MyHeap(int maxHeapSize) {heapArray = new int[maxHeapSize + 1];heapSize = 0;heapArray[0] = Integer.MIN_VALUE; // 使用哨兵元素，简化索引计算}public MyHeap(int[] nums) {heapArray = new int[nums.length + 1];System.arraycopy(nums, 0 , heapArray, 1, nums.length);heapSize = nums.length;heapArray[0] = Integer.MIN_VALUE; // 使用哨兵元素，简化索引计算for(int i = heapSize / 2; i >= 1; i --) {minHeapify(i);}}// 向堆中插入一个元素public void insert(int value) {if (heapSize == heapArray.length - 1) {throw new IllegalStateException("Heap is full.");}heapSize++;heapArray[heapSize] = value;int current = heapSize;while (heapArray[current] < heapArray[current / 2]) {swap(current, current / 2);current = current / 2;}}// 删除并返回堆中的最小元素public int top() {if (isEmpty()) {throw new IllegalStateException("Heap is empty.");}int root = heapArray[1];heapArray[1] = heapArray[heapSize];heapSize--;minHeapify(1);return root;}// 查看堆顶元素public int peek() {if (isEmpty()) {throw new IllegalStateException("Heap is empty.");}return heapArray[1];}// 检查堆是否为空public boolean isEmpty() {return heapSize == 0;}// 调整堆，使其满足小根堆性质private void minHeapify(int index) {int left = 2 * index;int right = 2 * index + 1;int smallest = index;if (left <= heapSize && heapArray[left] < heapArray[index]) {smallest = left;}if (right <= heapSize && heapArray[right] < heapArray[smallest]) {smallest = right;}if (smallest != index) {swap(index, smallest);minHeapify(smallest);}}// 交换两个元素的位置private void swap(int i, int j) {int temp = heapArray[i];heapArray[i] = heapArray[j];heapArray[j] = temp;}// 主函数用于测试public static void main(String[] args) {int[] nums = new int[]{3,1,9,5,4,6,7,2,0,8};MyHeap minHeap = new MyHeap(nums);while(!minHeap.isEmpty()) {System.out.println(minHeap.top());}}
}