数据结构-堆

宅蓝三木

发布于 2024-10-09 21:21:10

19200

代码可运行

文章被收录于专栏：三木的博客三木的博客

运行总次数：0

代码可运行

堆的定义

堆（Heap）是一种特殊的树形数据结构，通常是一个完全二叉树。在堆中，每个节点都满足堆的性质：

最大堆：父节点的值大于或等于其所有子节点的值。例如，在最大堆中，根节点是整个堆中的最大值。
最小堆：父节点的值小于或等于其所有子节点的值。在最小堆中，根节点是整个堆中的最小值。

堆的存储

堆通常使用数组来实现存储。对于完全二叉树，假设根节点存储在数组索引为 0 的位置，对于任意节点存储在数组索引为 i 的位置：

它的左子节点存储在数组索引为 2 * i + 1 的位置。
它的右子节点存储在数组索引为 2 * i + 2 的位置。
它的父节点存储在数组索引为 (i - 1) // 2 的位置（向下取整）。

堆的基本操作

插入元素：

先将新元素添加到堆的末尾（数组的最后一个位置）。
然后将新元素与其父节点进行比较，如果不满足堆的性质，则与父节点交换位置。
重复这个过程，直到新元素满足堆的性质或者到达根节点。

删除元素：

在最大堆中，删除操作通常是删除根节点（最大值）。将根节点与堆的最后一个元素交换位置，然后删除最后一个元素。
新的根节点可能不满足堆的性质，需要将其与子节点进行比较并交换，直到满足堆的性质。这个过程称为堆化（Heapify）。

构建堆：

可以从一个无序的数组构建堆。从最后一个非叶子节点开始，对每个非叶子节点执行堆化操作，直到整个数组满足堆的性质。

堆的应用场景

堆排序：利用堆的性质进行排序。可以在O(nlogn)时间复杂度内对数组进行排序。
优先队列：堆可以高效地实现优先队列。优先队列是一种数据结构，其中每个元素都有一个优先级，元素按照优先级出队。例如，在操作系统中，任务调度可以使用优先队列，高优先级的任务先执行。
Dijkstra 算法：用于在图中求单源最短路径，算法中使用最小堆来存储未确定最短路径的节点，每次从堆中取出距离源点最短距离的节点进行松弛操作。

前K个高频元素

Link: https://leetcode.cn/problems/g5c51o/description/

def heapAppend(heap, nMap, num):
    heap.append(num)
    cur = len(heap) - 1
    parent = (cur - 1) // 2
    while parent >= 0:
        if nMap[heap[cur]] < nMap[heap[parent]]:
            heap[cur], heap[parent] = heap[parent], heap[cur]
        cur = parent
        parent = (cur - 1) // 2

def heapify(heap, nMap, i):
    if i >= len(heap):
        return
    leftChild = 2 * i + 1
    rightChild = 2 * i + 2
    minEle = i
    if leftChild < len(heap) and nMap[heap[leftChild]] < nMap[heap[minEle]]:
        minEle = leftChild
    if rightChild < len(heap) and nMap[heap[rightChild]] < nMap[heap[minEle]]:
        minEle = rightChild
    if minEle != i:
        heap[minEle], heap[i] = heap[i], heap[minEle]
        heapify(heap, nMap, minEle)

def stack(heap, nMap, k):
    for num in nMap.keys():
        if len(heap) < k:
            heapAppend(heap, nMap, num)
        else:
            if nMap[num] < nMap[heap[0]]:
                continue
            else:
                heap[0] = num
                heapify(heap, nMap, 0)

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        nMap = {}
        heap = []
        for num in nums:
            if num not in nMap:
                nMap[num] = 1
            else:
                nMap[num] += 1
        stack(heap, nMap, k)
        return heap

用Python的heapq实现：

import heapq

def stack(heap, nMap, k):
    for num in nMap.keys():
        if len(heap) < k:
            heapq.heappush(heap, (nMap[num], num))
        else:
            if nMap[num] < heap[0][0]:
                continue
            else:
                heapq.heapreplace(heap, (nMap[num], num))

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        nMap = {}
        heap = []
        for num in nums:
            if num not in nMap:
                nMap[num] = 1
            else:
                nMap[num] += 1
        stack(heap, nMap, k)
        return [x[1] for x in heap]

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-09-15，如有侵权请联系 cloudcommunity@tencent.com 删除

数据结构