当前位置： 首页 >> 数据结构与算法 >> 堆和堆排序

---

堆和堆排序

2020-07-04 18:57:40 星期六  阅读：1740

---

####堆是一种特殊的树 一棵树，只要满足如下两点，它就是一个堆： 堆是一个完全二叉树（除了最后一层，其他层都必须是满的）。 堆中的每个节点的值都必须大于等于（或小于等于）其子树中的每个节点。 `大顶堆`：每个节点的值都大于等于子树 中每个节点的值； `小顶堆`：每个节点的值都小于等于子树中每个节点的值； ####关于堆的一些操作 ` 实现一个堆` - 因为堆是一种完全二叉树，所以比较适合用数组来存储； ` 堆化` - 当往堆里插入或者删除一个元素的时候，需要调整堆中的各个元素的位置，以满足堆的定义。这个调整的过程就是堆化的过程。 - - 堆化其实就是顺着节点所在的路径，向上或者向下对比，然后交换。 `往堆中插入一个元素` - 把新插入的元素放在堆的最后，然后再使用自下往上的方法进行调整。直到父子之间满足堆的两个特性。 `删除堆顶元素` - 删除堆顶元素之后，就需要把第二大的元素放在堆顶。从上往下法进行调整 因为对于n个节点，树的高度不会超过log2n，所以堆化的时间复杂度跟树的高度成正比，也就是O(logn)。 ####堆排序 #####建堆 首先将需要排序的数组原地建成一个堆，就在原数组上进行操作；有两种思路： 从前往后处理：借助上面讲的往堆里插入一个元素的方法，假设最开始只有一个元素，依次往里面插入。 从后往前处理 建堆的时间复杂度 因为需要遍历需要排序的所有数据，所以时间复杂度为O(n)。 ####排序 建堆结束之后，数组中的数据已经是按照大顶堆的特性来组织的，数组中的第一个元素就是堆顶。也就是最大的元素。把堆顶放到最后一个位置（下标为n的位置），然后再从剩下的元素里找到最大值（也即是堆顶）。再把最大值放到n - 1的位置。这样层层遍历，直到堆中只有最后一个元素，最后就得到了排序结果 ####堆排序的特性 原地排序算法 建堆过程的时间复杂度是O(n) 排序过程的时间复杂度是O(nlogn) 整体的时间复杂度为O(nlogn) 堆排序不是稳定排序算法 ####为什么快速排序要比堆排序性能好？ 堆排序数据访问的方式没有快速排序友好 因为堆是跳着下标访问的，所以堆CPU缓存不太友好； 堆排序算法的数据交换次数要多于快速排序； ####堆排序代码实现 ``` # 堆化函数（把一个普通数组转化为堆），传入需要堆化的数组 def arr2heap(arr): heap = [None] * (len(arr) + 1) # 创建一个堆数组，大小为原始数组+1，因为堆的第一个元素（下标为0）是None heap[1] = arr[0] # 堆顶元素赋初始值 for i in range(1, len(arr)): n = i + 1 # 堆数组的下标 heap[n] = arr[i] # 把新的元素放在堆的末尾 while (n > 1): parent = n // 2 # 当前节点的父节点堆的下标 if heap[n] > heap[parent]: # 判断当前节点是否大于父节点。如果大，则交换节点的值 tmp = heap[n] heap[n] = heap[parent] heap[parent] = tmp n = n // 2 # 依次往上遍历，直到当前节点的值小于父节点的值 else: break return heap # 堆排序，传入需要排序的数组 def heap_sort(arr): n = len(arr) - 1 # 对数组操作的游标 heap = arr2heap(arr) # 建堆（堆化） while (True): arr[n] = heap[1] # 堆顶元素为当前最大的元素，直接插入末尾 heap[1] = heap[n + 1] # 把最后一个元素当做当前堆顶元素 heap.pop(n + 1) # 删除堆的最后一个元素 nums = heap[1:] # 把当前的堆转化为数组 heap = arr2heap(nums) # 调用堆化函数重新堆化 n -= 1 if len(heap) == 2: # 如果只有堆顶元素，则该元素已经是最小的元素，直接插入数组即可推出循环 arr[n] = heap[1] break return arr arr = [6, 3, 5, 2, 8, 4, 7, 10, 3, 9, 4, 1, 1, 3, 281, 13, 1] t = heap_sort(arr) print(t) # 输出结果如下 # [1, 1, 1, 2, 3, 3, 3, 4, 4, 5, 6, 7, 8, 9, 10, 13, 281] ``` ####堆的应用 #####优先级队列 合并有序小文件 把100个小文件合并成一个有序的大文件（每个小文件内部有序），从这100个文件中，各取一个字符串，放入数组中，比较大小。将最小的哪个字符串放入合并后的大文件中，并从数组中删除。 高性能定时器 按照任务的优先级将任务存储在优先级队列中，队列首部（也就是小顶堆的堆顶）存储的就是最先执行的任务，当调度器只需要看当前堆顶的任务是否满足执行时间的条件，不需要遍历所有任务，所以性能会非常高。 ####利用堆求topK 针对静态数据集合 维护一个大小为K的小顶堆，顺序遍历数组，从数组中取出数据与堆顶元素进行比较。如果比堆顶元素大，我们就把堆顶元素删除，并将这个元素插入堆中。否则，不做处理，等数组遍历完后，这个小顶堆就是TopK的数据。 针对动态数据集合 还是维护一个大小为K的小顶堆。当有数据被添加到数组中时，我们就拿它与当前堆顶元素进行对比； ####利用堆求中位数 大概思想是：我们需要维护两个堆，一个大顶堆，一个小顶堆。大顶堆中存储前半部分数据，小顶堆中存储后半部分数据，且小顶堆中的数据都大于大顶堆中的数据。不管n是奇数还是偶数，大顶堆的堆顶元素就是中位数。 对于动态的数据，每次插入或者删除数据都会涉及到堆化操作，根据插入数据与当前两个堆的堆顶进行对比，决定插入到哪个堆中。如果两个堆中的数据个数不符合前面的情况，则需要从一个堆中不停的搬移堆顶元素到另一个堆，使其保证大顶堆的堆顶元素是中位数。 ####实例 有一个包含10亿个搜索关键词的日志文件，如何快速获取到top10最热门的搜索关键词呢？ 限定条件：内存1GB 分析方法：10个亿的日志文件最小8GB，最大则不好说。所以，可以通过散列表来记录关键词的出现次数，具体的实现过程如下： 顺序扫描10亿个搜索关键词； 扫描到某个关键词的时候去散列表里查，如果存在就将该关键词的计数器+1；如果不存储在就插入散列表并记录计数器1； 遍历完10亿关键词后就得到了每个关键词搜索次数的散列表； 使用上面介绍的用堆求TopK的方法，维护一个大小为K的小顶堆，遍历散列表；直到遍历结束； 使用这种方法有一个弊端，如果不重复的关键词的个数很多，比如10亿条日志文件中有1亿个，那散列表的大小肯定超过1个GB，导致内存不够。所以，需要更好的方案来做： 将10亿关键词分片到10个文件中； 针对每个小文件，利用散列表和堆，分别求出top10； 然后再把这10个top10（100个关键词）对比求出最终的top10。