Leetcode部分堆相关练习

一、堆1. 定义2. 实现一个小顶堆、大顶堆、优先级队列2.1 小顶堆2.2 大顶堆2.3 优先级队列 3. 实现堆排序4. 利用优先级队列合并 K 个有序数组5. 求一组动态数据集合的最大 Top K6. 练习112. 路径总和

一、堆

1. 定义

1、堆是一棵完全二叉树，这棵二叉树需要满足堆序：任何分支结点（即除去叶结点所剩余的结点）的值都大于等于（或小于等于）其左右子结点的值。

2、一般用列表来表示堆（Python中的列表下标从0开始），i结点的父结点位置为$(i-1)//2$(取整)，i结点的左右子结点位置为$2\ast i+1$和$2\ast i+2$。

3、如果堆序是小元素优先，则构造出来的称为‘小顶堆’（小元素在上）；如果堆序是大元素优先，则构造出来的称为‘大顶堆’（大元素在上）。

堆排序涉及到的概念

堆排序是利用堆进行排序的堆是一种完全二叉树堆有两种类型: 大顶堆 小顶堆

两种类型的概念如下：

大顶堆：每个结点的值都大于或等于左右孩子结点小顶堆：每个结点的值都小于或等于左右孩子结点

2. 实现一个小顶堆、大顶堆、优先级队列

2.1 小顶堆

给出N长的序列，求出TopK大的元素，使用小顶堆，heapq模块实现。

import sys import heapq class TopKHeap(object): def __init__(self, k): self.k = k self.data = [] def push(self, elem): if len(self.data) < self.k: heapq.heappush(self.data, elem) else: topk_small = self.data[0] if elem > topk_small: heapq.heapreplace(self.data, elem) def topk(self): return [x for x in reversed([heapq.heappop(self.data) for x in xrange(len(self.data))])] def main(): list_num = [1, 2, 3, 4, 5, 6, 7, 8, 9] th = TopKHeap(5) for i in list_num: th.push(i) print th.topk() if __name__ == "__main__": main()

2.2 大顶堆

[https://www.jianshu.com/p/d174f1862601]

首先将待排序的数组构造出一个大顶堆取出这个大顶堆的堆顶节点(最大值)，与堆的最下最右的元素进行交换，然后把剩下的元素再构造出一个大顶堆重复第二步，直到这个大顶堆的长度为1，此时完成排序。

第二步骤

这就是构建大顶堆的思想，了解了之后就可以进行编码，编码主要解决两个问题：

如何把一个序列构造出一个大顶堆输出堆顶元素后，如何使剩下的元素构造出一个大顶堆 from collections import deque def swap_param(L, i, j): L[i], L[j] = L[j], L[i] return L def heap_adjust(L, start, end): temp = L[start] i = start j = 2 * i while j <= end: if (j < end) and (L[j] < L[j + 1]): j += 1 if temp < L[j]: L[i] = L[j] i = j j = 2 * i else: break L[i] = temp def heap_sort(L): L_length = len(L) - 1 first_sort_count = L_length / 2 for i in range(first_sort_count): heap_adjust(L, first_sort_count - i, L_length) for i in range(L_length - 1): L = swap_param(L, 1, L_length - i) heap_adjust(L, 1, L_length - i - 1) return [L[i] for i in range(1, len(L))] def main(): L = deque([50, 16, 30, 10, 60, 90, 2, 80, 70]) L.appendleft(0) print heap_sort(L) if __name__ == '__main__': main() # 更简单的方法 同上小顶堆 # 给出N长的序列，求出BtmK小的元素，即使用大顶堆。 # 将push(e)改为push(-e)、pop(e)改为-pop(e) # 也就是说，在存入堆、从堆中取出的时候，都用相反数，而其他逻辑与TopK完全相同 class BtmkHeap(object): def __init__(self, k): self.k = k self.data = [] def Push(self, elem): # Reverse elem to convert to max-heap elem = -elem # Using heap algorighem if len(self.data) < self.k: heapq.heappush(self.data, elem) else: topk_small = self.data[0] if elem > topk_small: heapq.heapreplace(self.data, elem) def BtmK(self): return sorted([-x for x in self.data])

2.3 优先级队列

使用heapq模块实现的简单的优先队列

from heapq import * class Heap_Pri_Queue(object): def __init__(self, heap=[]): self.heap = heap heapify(self.heap) def enqueue(self, val): heappush(self.heap, val) def dequeue(self): return heappop(self.heap) if __name__ == "__main__": lst = [5, 6, 8, 1] heap = Heap_Pri_Queue(lst) print(heap.dequeue()) #1 heap.enqueue(3) print(heap.heap) #[3, 5, 8, 6]

3. 实现堆排序

思路：

建立堆得到堆顶元素，为最大元素去掉堆顶，将堆最后一个元素放到堆顶，此时可通过一次调整重新使堆有序堆顶元素为第二大元素重复步骤3，直到堆变空 def sift(data, low, high): i = low # 父节点 j = 2 * i + 1 # 左子节点 tmp = data[i] # 父节点值 while j <= high: # 子节点在节点中 if j < high and data[j] > data[j + 1]: # 有右子节点且右节点比父节点值大 j += 1 if tmp > data[j]: data[i] = data[j] # 将父节点替换成新的子节点的值 i = j # 变成新的父节点 j = 2 * i + 1 # 新的子节点 else: break data[i] = tmp # 将替换的父节点值赋给最终的父节点 def heap_sort(data): n = len(data) # 创建堆 for i in range(n//2-1, -1, -1): sift(data, i, n-1) # 挨个出数 for i in range(n-1, -1, -1): # 从大到小 data[0], data[i] = data[i], data[0] # 将最后一个值与父节点交互位置 sift(data, 0, i-1) li = list(range(10)) random.shuffle(li) print(li) heap_sort(li) print(li)

4. 利用优先级队列合并 K 个有序数组

# 采用归并排序算法 # 拆解到最后，实际变成两个数组进行排序 def MergeSort(nums): # 请牢记传入的参数是多维数组 # 此处是递归结束条件 if len(nums) <= 1: return nums # 取中间位置 mid = len(nums) // 2 # 此处实现递归 # 记住此处得到的也是多维数组 Left = MergeSort(nums[:mid]) Right = MergeSort(nums[mid:]) # print(Left[0], Right[0]) # 要传入的参数是数组中第一个索引处的值 return Sort_list(Left[0], Right[0]) def Sort_list(Left, Right): # 存储排序后的值 res = [] a = 0 b = 0 while a < len(Left) and b < len(Right): if Left[a] < Right[b]: res.append(Left[a]) a += 1 else: res.append(Right[b]) b += 1 # 因为存在一个到终点后，另一个还没到终点 # 这时就需要将没到终点的剩下的值添加到数组中 while a < len(Left): res.append(Left[a]) a += 1 while b < len(Right): res.append(Right[b]) b += 1 # 将一维数组二维化 res = [res] return res if __name__ == '__main__': b = MergeSort([[1,2,3],[2,3,5],[6,7,9],[7,8,9],[3,5,6]]) print(b) ''' # 数组降维 a = [] for i in b[0]: a.append(i) print(a)

5. 求一组动态数据集合的最大 Top K

建立一个包括k个数小根堆，遍历数组，如果大于小根堆的堆顶，替换，重新构建小根堆。

import heapq def findKthLargest(self, nums, k): """ :type nums: List[int] :type k: int :rtype: int """ return heapq.nlargest(k, nums)[-1] # 不调用库 def findKthLargest(self, nums, k): """ :type nums: List[int] :type k: int :rtype: int """ #先将前k个数变成小根堆 nums = self.heapInsert(nums, k) for i in range(k, len(nums)): if nums[i] > nums[0]: nums = self.heapify(nums, nums[i], k) return nums[0] def heapInsert(self, nums, k): """ 将列表转变为小根堆 """ for index in range(1, k): while nums[(index - 1) // 2] > nums[index] and index > 0: nums[(index - 1) // 2], nums[index] = \ nums[index], nums[(index - 1) // 2] index = (index - 1) // 2 return nums def heapify(self, nums, new_val, k): """ 小根堆nums的堆顶变成new_val，重新生成小根堆 """ head = 0 nums[head] = new_val l = 1 while l < k: r = l + 1 if r >= k: small = l else: if nums[l] <= nums[r]: small = l else: small = r if nums[head] < nums[small]: break nums[head], nums[small] = nums[small], nums[head] head = small l = head * 2 + 1 return nums

6. 练习

112. 路径总和

[https://leetcode-cn.com/problems/path-sum/] 题目描述 给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。

说明: 叶子节点是指没有子节点的节点。

代码实现

# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def hasPathSum(self, root: TreeNode, sum: int) -> bool: if not root: return False if root.val == sum and (not root.left and not root.right): return True else: return(self.hasPathSum(root.left, sum-root.val) or self.hasPathSum(root.right, sum-root.val))