算法刻意练习之堆/二叉堆

梦里梦外; 2022-12-06 15:14 212阅读 0赞

## 1 堆 Heap ##

### 1.1 特点 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4_size_16_color_FFFFFF_t_70_pic_center]

## 2 二叉堆 Binary Heap ##

### 2.1 特点 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4_size_16_color_FFFFFF_t_70_pic_center 1]

### 2.2 注意![在这里插入图片描述][20200926141829540.png_pic_center] ###

### 2.2 递归状态树 ###

（1）大顶堆  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4_size_16_color_FFFFFF_t_70_pic_center 2]  
（2）大顶堆和小顶堆存储模式  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4_size_16_color_FFFFFF_t_70_pic_center 3]

### 2.3 实现和细节 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4_size_16_color_FFFFFF_t_70_pic_center 4]

## 3 二叉堆的增删查 ##

### 3.1 插入-O(logN) ###

（1）特点  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4_size_16_color_FFFFFF_t_70_pic_center 5]  
（2）步骤演示  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4_size_16_color_FFFFFF_t_70_pic_center 6]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4_size_16_color_FFFFFF_t_70_pic_center 7]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4_size_16_color_FFFFFF_t_70_pic_center 8]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4_size_16_color_FFFFFF_t_70_pic_center 9]

### 3.1 删除-O(logN) ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4_size_16_color_FFFFFF_t_70_pic_center 10]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4_size_16_color_FFFFFF_t_70_pic_center 11]

### 3.3 查找最大最小值-O(1) ###

## 4 堆的经典算法题 ##

[347. 前 K 个高频元素][347. _ K]

/**
         * 347. 前 K 个高频元素  nums = [0, 0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 4, 4, 5, 5, 6] , k = 2
         *
         * 思路：如果堆的元素个数小于k，就可以直接插入堆中。
         *      如果堆的元素个数等于k，则检查堆顶与新元素的次数的大小。如果堆顶更大，说明至少有k个数字的出现次数比当前值大，故舍弃当前值；否则，就弹出堆顶，并将当前值插入堆中。
         *
         * 时间复杂度：O(nlogk)。维护一个大小为k的小顶堆，每次插入元素的时候，需要的时间是logk；
         *          而整个过程中处理n个元素，最坏的情况就是，每次如果新元素的次数比堆顶端的元素大，
         *          则弹出堆顶端的元素，将新的元素添加进堆中，这个过程总共需要做n次，结果是nlogk
         *
         * 空间复杂度：O(n)，最坏情况下（每个元素都不同），map需要存储n个键值对，优先队列需要存储k个元素，
         *          因此空间复杂度是O(n)。
         *
         * https://leetcode-cn.com/problems/top-k-frequent-elements/solution/347-qian-k-ge-gao-pin-yuan-su-by-chen-li-guan/
         * @param nums
         * @param k
         * @return
         */
        @RequiresApi(Build.VERSION_CODES.N)
        fun topKFrequent(nums: IntArray, k: Int): MutableList<Int> {
            val res: MutableList<Int> = mutableListOf()
            if (nums.isEmpty()) return res
    
            // 1. 使用map统计每个元素出现的次数：元素为键，元素出现的次数为值
            val map: MutableMap<Int, Int> = mutableMapOf()
            for (num in nums) {
                if (map.containsKey(num)) {
                    map[num] = map[num]!! + 1
                } else {
                    map[num] = 1
                }
            }
    
            // 2.1 优先堆队列：按升序用小顶堆保存次数最大的k个元素
            val heap = PriorityQueue(Comparator<Int> { o1, o2 -> map[o1]!! - map[o2]!! })
            for (key in map.keys) {
                if (heap.size < k) {
                    // 2.2 如果堆的元素个数小于k：
                    // 就可以直接插入堆中
                    heap.offer(key)
                } else if (map[key]!! > map[heap.peek()]!!) {
                    // 2.3 如果堆的元素个数等于k：如果新元素的次数比堆顶端的元素大，则弹出堆顶端的元素，将新的元素添加进堆中
                    heap.poll()
                    heap.offer(key)
                }
            }
    
            // 3. 最小堆中的k个元素即为前k个高频元素，遍历取出堆中的元素
            for (i in heap) {
                res.add(i)
            }
            return res
        }

## 5 堆的实现代码 ##

class BinaryHeap(capacity: Int) {
    
        private val d = 2
        private var heap: IntArray
        private var heapSize = 0
    
        /**
         * 这将使用默认大小初始化我们的堆。
         */
        init {
            heapSize = 0
            heap = IntArray(capacity + 1)
            Arrays.fill(heap, -1)
        }
    
        fun isEmpty(): Boolean {
            return heapSize == 0
        }
    
    
        fun isFull(): Boolean {
            return heapSize == heap.size
        }
    
        private fun parent(i: Int): Int {
            return (i - 1) / d
        }
    
        private fun kthChild(i: Int, k: Int): Int {
            return d * i + k
        }
    
        /**
         * 在堆中插入新元素
         * 时间复杂性: O(log N)，在最坏的情况下，我们需要遍历到根本
         */
        fun insert(x: Int) {
            if (isFull()) {
                throw NoSuchElementException("Heap is full, No space to insert new element")
            }
            heap[heapSize] = x
            heapSize++
            heapifyUp(heapSize - 1)
        }
    
        /**
         * 删除索引为x的元素
         * Complexity: O(log N)
         */
        fun delete(x: Int): Int {
            if (isEmpty()) {
                throw NoSuchElementException("Heap is empty, No element to delete")
            }
            val maxElement = heap[x]
            heap[x] = heap[heapSize - 1]
            heapSize--
            heapifyDown(x)
            return maxElement
        }
    
    
        /**
         * 插入元素时保持堆属性。
         */
        private fun heapifyUp(i: Int) {
            var i = i
            val insertValue = heap[i]
            while (i > 0 && insertValue > heap[parent(i)]) {
                heap[i] = heap[parent(i)]
                i = parent(i)
            }
            heap[i] = insertValue
        }
    
    
        /**
         * 在删除元素时保持堆属性。
         */
        private fun heapifyDown(i: Int) {
            var i = i
            var child: Int
            val temp = heap[i]
            while (kthChild(i, 1) < heapSize) {
                child = maxChild(i)
                if (temp >= heap[child]) {
                    break
                }
                heap[i] = heap[child]
                i = child
            }
            heap[i] = temp
        }
    
    
        private fun maxChild(i: Int): Int {
            val leftChild = kthChild(i, 1)
            val rightChild = kthChild(i, 2)
            return if (heap[leftChild] > heap[rightChild]) leftChild else rightChild
        }
    
    
        /**
         * 打印堆的所有元素
         */
        fun printHeap() {
            print("nHeap = ")
            for (i in 0 until heapSize) print(heap[i].toString() + " ")
            println()
        }
    
    
        /**
         * 此方法返回堆的max元素。
         * complexity: O(1)
         */
        fun findMax(): Int {
            if (isEmpty()) throw NoSuchElementException("Heap is empty.")
            return heap[0]
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/c6935c6a725e496dab32f2dfa3d1af31.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/72708fce0f5940fdbf6d23ff541dd899.png
[20200926141829540.png_pic_center]: /images/20221123/de7f19667630405ea6e2784dc7fc67e1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221123/787b819f3ae347d693a5a75ea983984a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221123/4708bdfea0ca45e9b273d9d59be790bd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221123/b991f98bf12b472c86b32aebabbf6fe5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221123/71b8d4a9ca064d5bbc94c573b424113f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4_size_16_color_FFFFFF_t_70_pic_center 6]: /images/20221123/3a225208bd024e3295216320625b2f0e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4_size_16_color_FFFFFF_t_70_pic_center 7]: /images/20221123/414f9a6de8c34d4fa49d5112b1429f61.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4_size_16_color_FFFFFF_t_70_pic_center 8]: /images/20221123/871af2c0ce364b2790d22b3ea44b17fe.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4_size_16_color_FFFFFF_t_70_pic_center 9]: /images/20221123/601decb4ea834ddf8d66893c5b253bd7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4_size_16_color_FFFFFF_t_70_pic_center 10]: /images/20221123/26af18e70b734b42ae2a5978d1b72472.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4_size_16_color_FFFFFF_t_70_pic_center 11]: /images/20221123/e8e333eff3a549bfa671f8055b4644d2.png
[347. _ K]: https://leetcode-cn.com/problems/top-k-frequent-elements/solution/347-qian-k-ge-gao-pin-yuan-su-by-chen-li-guan/