珠海响应式网站建设,wordpress模板 古典,吴江区建设银行招聘网站,可以做平面设计兼职的网站堆#xff08;heap#xff09;
堆的概念#xff1a;
是完全二叉树#xff1b;每个节点 或 孩子节点。
条件二中分别对应#xff1a;最大堆和最小堆。
最大堆#xff1a;最大值为堆顶元素#xff0c;每个节点 孩子节点。 最小堆#xff1a;最小值为堆…堆heap
堆的概念
是完全二叉树每个节点 或 孩子节点。
条件二中分别对应最大堆和最小堆。
最大堆最大值为堆顶元素每个节点 孩子节点。 最小堆最小值为堆顶元素每个节点 孩子节点。 python中的堆
python中只能直接创建最小堆。如果想要创建最大堆可以先将所有元素乘负一(取反)然后最小堆化取元素的时候再取反这样相当于得到最大堆。
应用top – K、第K个最大值每次可以取出最大最小元素
堆化把一组无序的数加到堆里面。 注意堆化操作的时间复杂度为O(N)排序算法的时间复杂度为O(NlogN)
引入方法将列表堆化再进行相关操作。 Import heapq heap [ ]
heapq.heapify(heap)将堆属性应用到列表上(堆化操作)。heapq.heappush(heap, item)将 item 元素加入堆。heapq.heappop(heap)弹出堆顶元素也就是最小值heapq.heapreplace(heap, x)弹出堆顶元素并将元素x 入堆。heapq.merge(*iterables, keyNone, reverseFalse)将多个有序的堆合并成一个大的有序堆然后再输出。heapq.heappushpop(heap, item)将item 入堆然后弹出并返回堆中最小的元素。heapq.nlargest(n, iterable, keyNone)返回堆中最大的 n 个元素。heapq.nsmallest(n, iterable, keyNone)返回堆中最小的 n 个元素。
代码实战
实战一用最小堆解决数组中第K个最大元素的问题。 代码部分
import heapq
class Solution:def findKthLargest(self, nums: List[int], k: int) - int:# 最小堆把n-k小的元素都取出来下一次取的时候就是第K个最大值了heapq.heapify(nums)while len(nums) k:heapq.heappop(nums)return nums[0]实战二用哈希表 最小堆 解决前K高频单词的问题 代码部分方法二待更新……
class Solution:def topKFrequent(self, words: List[str], k: int) - List[str]:# 方法一哈希表 排序count {}for word in words:count[word] count.get(word,0) 1sorted_list sorted(count.items(), keylambda item: (-item[1], item[0]))return [item[0] for item in sorted_list][:k]# 方法二哈希表 最小堆 待更新……import heapq参考资料
leetcode 题库例题
