你知道什么是堆吗？有什么用处？

墨蓝 2024-05-04 08:12 184阅读 0赞

![在这里插入图片描述][f2dc69c781c5494c889df30db2565bc2.png]

> ?**博主介绍**： 博主从事应用安全和大数据领域，有8年研发经验，5年面试官经验，Java技术专家，WEB架构师，阿里云专家博主，华为云云享专家，51CTO 专家博主

⛪️ 个人社区：[个人社区][Link 1]  
? 个人主页：[个人主页][Link 2]  
? 专栏地址： ✅ [Java 中级][Java]  
?八股文专题：[剑指大厂，手撕 Java 八股文][Java 1]

#### 文章目录 ####

*   *   *  1. 什么是堆？
         *  2. 堆的分类
         *  3. 堆的应用场景，解决了什么问题
         *  4. 用 java 实现一个堆
         *  5. 的原理
         *  6. 用堆解决的算法问题 - 数组中的第K个最大元素

#### 1. 什么是堆？ ####

堆是一种数据结构，用于存储和组织数据。堆通常用于实现优先队列，其中具有最高（或最低）优先级的元素始终位于堆的顶部。堆分为最大堆和最小堆，最大堆中父节点的值大于或等于其子节点的值，而最小堆中父节点的值小于或等于其子节点的值。堆具有快速的插入和删除操作的优点，通常用于解决一些重要的算法问题。

堆一般是一个完全二叉树，所谓的完全二叉树就是指除了叶子节点外，其他节点都是满二叉树，也就是其他节点都是既有左节点，又有右节点的，完全二叉树如下所示：

![在这里插入图片描述][40fa9983262b42dead5a56c1cff86b70.png]

#### 2. 堆的分类 ####

堆可以分为两种主要类型：最大堆和最小堆。

1.  最大堆（Max Heap）：
    
     *  最大堆是一种堆，其中父节点的值始终大于或等于其子节点的值。
     *  在最大堆中，根节点的值最大，因此也称为最大堆。
     *  通过维护这种性质，可以实现高效地获取最大值的操作。
     *  最大堆通常用于实现优先队列，其中具有最高优先级的元素位于堆的顶部。
2.  最小堆（Min Heap）：
    
     *  最小堆是一种堆，其中父节点的值始终小于或等于其子节点的值。
     *  在最小堆中，根节点的值最小，因此也称为最小堆。
     *  通过维护这种性质，可以实现高效地获取最小值的操作。
     *  最小堆通常用于实现优先队列，其中具有最低优先级的元素位于堆的顶部。

无论是最大堆还是最小堆，它们都具有类似的数据结构，通常使用完全二叉树的形式来表示。堆的插入和删除操作通常会触发堆的重新调整，以保持堆的性质。堆是一种常用的数据结构，广泛应用于算法和数据处理领域。

#### 3. 堆的应用场景，解决了什么问题 ####

堆在计算机科学中有许多应用场景，主要用于解决以下问题：

1.  优先队列：堆可以用来实现优先队列，其中具有最高（或最低）优先级的元素始终位于堆的顶部。这种数据结构在很多算法中都有重要应用，如Dijkstra算法、Prim算法等。
2.  堆排序：堆排序是一种高效的排序算法，利用最大堆或最小堆来实现排序。堆排序的时间复杂度为O(nlogn)，且具有原地排序的特点。
3.  事件驱动系统：堆可以用来实现事件驱动系统，根据事件的优先级来处理事件。例如，操作系统中的任务调度、网络路由中的数据包处理等都可以利用堆来实现。
4.  中位数查找：使用两个堆（一个最大堆和一个最小堆）可以高效地实现动态数据流中的中位数查找操作。
5.  堆化：堆化操作可以将一个无序数组转换为一个堆，从而可以快速地进行插入、删除等操作。

#### 4. 用 java 实现一个堆 ####

import java.util.Arrays;
    
    public class MinHeap {
        
        private int[] heap;
        private int size;
        private int capacity;
    
        public MinHeap(int capacity) {
        
            this.capacity = capacity;
            this.size = 0;
            this.heap = new int[capacity];
        }
    
        public void insert(int value) {
        
            if (size == capacity) {
        
                System.out.println("Heap is full, cannot insert more elements.");
                return;
            }
    
            size++;
            int index = size - 1;
            heap[index] = value;
    
            while (index != 0 && heap[parent(index)] > heap[index]) {
        
                swap(index, parent(index));
                index = parent(index);
            }
        }
    
        public int extractMin() {
        
            if (size <= 0) {
        
                System.out.println("Heap is empty, cannot extract minimum element.");
                return -1;
            }
    
            if (size == 1) {
        
                size--;
                return heap[0];
            }
    
            int min = heap[0];
            heap[0] = heap[size - 1];
            size--;
            minHeapify(0);
    
            return min;
        }
    
        private void minHeapify(int index) {
        
            int left = leftChild(index);
            int right = rightChild(index);
            int smallest = index;
    
            if (left < size && heap[left] < heap[smallest]) {
        
                smallest = left;
            }
    
            if (right < size && heap[right] < heap[smallest]) {
        
                smallest = right;
            }
    
            if (smallest != index) {
        
                swap(index, smallest);
                minHeapify(smallest);
            }
        }
    
        private int parent(int i) {
        
            return (i - 1) / 2;
        }
    
        private int leftChild(int i) {
        
            return 2 * i + 1;
        }
    
        private int rightChild(int i) {
        
            return 2 * i + 2;
        }
    
        private void swap(int i, int j) {
        
            int temp = heap[i];
            heap[i] = heap[j];
            heap[j] = temp;
        }
    
        public void printHeap() {
        
            System.out.println(Arrays.toString(heap));
        }
    
        public static void main(String[] args) {
        
            MinHeap minHeap = new MinHeap(10);
            minHeap.insert(3);
            minHeap.insert(2);
            minHeap.insert(1);
            minHeap.insert(7);
            minHeap.insert(8);
    
            System.out.print("Heap: ");
            minHeap.printHeap();
    
            System.out.println("Extracted min element: " + minHeap.extractMin());
    
            System.out.print("Heap after extraction: ");
            minHeap.printHeap();
        }
    }

以上实现了一个最小堆（MinHeap）类，包含了插入元素、提取最小元素、最小堆化等操作。

#### 5. 的原理 ####

#### 6. 用堆解决的算法问题 - 数组中的第K个最大元素 ####

算法地址：[https://leetcode.cn/problems/kth-largest-element-in-an-array/description/][https_leetcode.cn_problems_kth-largest-element-in-an-array_description]

实现如下：

package com.jilu.camp.数组中的第K个最大元素;
    
    public class Solution {
        
    
        public int findKthLargest(int[] nums, int k) {
        
            int heapSize = nums.length;
    
            // 建堆
            buildMaxHeap(nums, heapSize);
            for (int i = nums.length - 1; i >= nums.length - k + 1; --i) {
        
                swap(nums, 0, i);
                --heapSize;
                maxHeapify(nums, 0, heapSize);
            }
            return nums[0];
        }
    
        public void buildMaxHeap(int[] a, int heapSize) {
        
            for (int i = heapSize / 2; i >= 0; --i) {
        
                maxHeapify(a, i, heapSize);
            }
        }
    
        public void maxHeapify(int[] a, int i, int heapSize) {
        
            int l = i * 2 + 1, r = i * 2 + 2, largest = i;
            if (l < heapSize && a[l] > a[largest]) {
        
                largest = l;
            }
            if (r < heapSize && a[r] > a[largest]) {
        
                largest = r;
            }
            if (largest != i) {
        
                swap(a, i, largest);
                maxHeapify(a, largest, heapSize);
            }
        }
    
        public void swap(int[] a, int i, int j) {
        
            int temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
    
        public static void main(String[] args) {
        
            Solution solution = new Solution();
            int[] nums = new int[]{
        3,2,1,5,6,4};
            System.out.println(solution.findKthLargest(nums, 2));
        }
    }

>  精彩专栏推荐订阅：在下方专栏??  
>  ✅ [2023年华为OD机试真题（A卷&B卷）+ 面试指导 ][2023_OD_A_B_ _]  
>  ✅ [ 精选100套 Java 项目案例 ][_100_ Java _]  
>  ✅ [面试需要避开的坑（活动）][Link 3]  
>  ✅ [你找不到的核心代码][Link 4]  
>  ✅ [带你手撕 Spring][Spring]  
>  ✅ [Java 初阶][Java 2]

![在这里插入图片描述][7b7478e55aa24a948b358051ef941b6a.webp_pic_center]

[f2dc69c781c5494c889df30db2565bc2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/04/22694772df344b13965834dd775ff48c.png
[Link 1]: https://bbs.csdn.net/forums/45c04d3f41cc4dadaf312be1d1379b45?category=10003
[Link 2]: https://jiliu.blog.csdn.net/
[Java]: https://blog.csdn.net/qq_37967783/category_12399402.html
[Java 1]: https://blog.csdn.net/qq_37967783/article/details/130940512
[40fa9983262b42dead5a56c1cff86b70.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/04/41bb0437fc6447d1b3e66c362a0d7b4b.png
[https_leetcode.cn_problems_kth-largest-element-in-an-array_description]: https://leetcode.cn/problems/kth-largest-element-in-an-array/description/
[2023_OD_A_B_ _]: https://blog.csdn.net/qq_37967783/category_12389634.html
[_100_ Java _]: https://blog.csdn.net/qq_37967783/category_12388267.html
[Link 3]: https://blog.csdn.net/qq_37967783/category_12380337.html
[Link 4]: https://blog.csdn.net/qq_37967783/category_12391346.html
[Spring]: https://blog.csdn.net/qq_37967783/category_12391987.html
[Java 2]: https://blog.csdn.net/qq_37967783/category_9902143.html
[7b7478e55aa24a948b358051ef941b6a.webp_pic_center]: https://img-blog.csdnimg.cn/7b7478e55aa24a948b358051ef941b6a.webp#pic_center