堆排序-最大／最小及应用

堆可以看成近似的完全二叉树。堆排序的时间复杂度是O(nlgn)。—输入的其实还是数组，只是一种结构–思想。 最上面的根结点i从序号0开始算起的话，那么左节点是2i+1, 右节点是2i+2；从1开始算起的话，那么就是2i, 2i+1。

堆的高度是lgn，堆包括大顶堆和小顶堆。 大顶堆每一个根结点都比其子节点大–最上面的根结点最大，小顶堆每一个根节点都比子节点小----最上面的根节点最小。

Max-Heapify就是在维护最大堆的过程，让A[i]逐级下降，做一个临近根结点和子节点的交换只需要O(1)的时间复杂度。 每个孩子节点的子树的大小至多为2/3n。 通过递归式子：T(n) <= T(2n/3) + O(1) 可以得： 最大堆的时间复杂度是T(n) = O(lgn) 也就是对于一个树高为h的最大堆来说，时间复杂度是O(h)。

构造一个最大堆的时间复杂度是O(n)

堆排序用的是最大堆，优先队列用的是最小堆。

堆排序的顺序就是 建堆—排除根----建堆(建堆就是从尾部开始heapify)

建堆

建最大堆的顺序是从左到右，从下到上，每一个向下移动都要跟最大的比，依次递归，直到比下面的大。 伪代码：输入数组A, 假定left(i)和right(i)都是最大堆,但是A(i)不一定构成最大堆。

—反正就是选择一个最大的作为largest，放在每棵树的根结点。

def Max_heapify(A, i): l = left(i) r = right(i) if l <= A.heap_size and A[l] > A[i]: largest = l else: largest = i if r <= A.heap_size and A[r] > A[largest]: largest = r if largest != i: exchange A[i] with A[largest] max_heapify(A, largest) def Build_max_heap(A): A.heap_size = A.length for i in range(A.length/2, 1): Max_heapify(A, i)

建堆是从左下角开始，依次往上，但是每次都会判断是否交换，交换后子树是否为最大堆，不是就递归下去。

堆排序

def Heap_sort(A): Build_max_heap(A) for i in range(A.length, 2): A[1], A[i] = A[i], A[1] A.heap_size = A.heap_size - 1 Max_heapify(A, 1)

交换之后还要麻烦Max_heapify(A, i)再排列成最大堆的形式。 序号很关键，通过画图可以得知，满二叉树每层的最左的节点的序号是上层的两倍或是两倍加1。

最大堆

def Heapify(A, i): heap_size = len(A) left = 2*i + 1 # 序号从0开始就是1； 根结点从1开始算起就是2*i right = 2*i + 2 # 序号从0开始就是2; 根结点从1开始算起就是2*i+1 largest = i if left < heap_size and A[left] > A[largest]: left, largest = largest, left if right < heap_size and A[right] > A[largest]: right, largest = largest, right if largest != i: A[i], A[largest] = A[largest], A[i] Heapify(A, largest) def Build_heap(A): #建堆从左下角开始 for i in range(len(A)//2, -1, -1): Heapify(A, i) def Heap_sort(A): sort_list = [] while len(A) > 0: # 每次排序拉取之后都要再次进行建堆。 Build_heap(A) sort_list.append(A[0]) A.pop(0) return sort_list A = [100, 200, 300, 2, 1, 3, 4, 7, 3, 7, 8, 1000] print(Heap_sort(A))

最小堆

def heapify(nums, index): left = 2 * index + 1 right = 2 * index + 2 minest = index if left < len(nums) and nums[minest] > nums[left]: minest, left = left, minest if right < len(nums) and nums[minest] > nums[right]: minest, right = right, minest if minest != index: nums[index], nums[minest] = nums[minest], nums[index] heapify(nums, minest) def build_heap(nums): for i in range(len(nums) // 2, -1, -1): heapify(nums, i) def Min_heap(nums, k): out = [] while len(nums) > 0: build_heap(nums) # 每删除一个就要选出一个小老弟。所以要重新排序。 out.append(nums[0]) nums.pop(0) return out

应用

对于 topk 问题：最大堆求topk小，最小堆求 topk 大。

topk小：构建一个 k 个数的最大堆，当读取的数小于根节点时，替换根节点，重新塑造最大堆 topk大：构建一个 k 个数的最小堆，当读取的数大于根节点时，替换根节点，重新塑造最小堆—当剩余的数目等于K的时候，那么就得到了想要的topk.

前 K 个高频元素

给定一个非空的整数数组，返回其中出现频率前 k 高的元素。

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2 输出: [1,2] 示例 2:

输入: nums = [1], k = 1 输出: [1]

你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。 你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的。 你可以按任意顺序返回

套用库

class Solution(object): def topKFrequent(self, nums, k): num_dict = {} for num in nums: if num not in num_dict: num_dict[num] = 1 else: num_dict[num] += 1 num_list = sorted(num_dict, key = lambda x : -num_dict[x]) # 加了负号就是从大到小， 注意此处变成了列表！！ return num_list[0:k]

最小堆

# 最小堆 class Solution(object): def topKFrequent(self, nums, k): num_dict = {} for num in nums: if num not in num_dict: num_dict[num] = 1 else: num_dict[num] += 1 # 次数不一定是唯一的 key_dict = {} num_list = [] for j in num_dict: if num_dict[j] not in key_dict: key_dict[num_dict[j]] = [j] else: key_dict[num_dict[j]].append(j) num_list.append(num_dict[j]) def Min_heap(nums, k): def heapify(nums, index): left = 2*index+1 right = 2*index+2 minest = index if left < len(nums) and nums[minest] > nums[left]: minest, left = left, minest if right < len(nums) and nums[minest] > nums[right]: minest, right = right, minest if minest != index: nums[index], nums[minest] = nums[minest], nums[index] heapify(nums, minest) def build_heap(nums): for i in range(len(nums)//2, -1, -1): heapify(nums, i) while len(nums) > k: build_heap(nums) # 注意是一上来就建堆。 nums.pop(0) return nums nums_out = Min_heap(num_list, k) out = [] for i in nums_out: out.append(key_dict[i][0]) if len(key_dict[i]) > 1: key_dict[i].pop(0) return out

快速排序

## 快速排序 class Solution(object): def topKFrequent(self, nums, k): def quick_partition(nums, index1, index2): index = index1 - 1 num_cmp = nums[index2] for i in range(index1, index2+1): if nums[i] <= num_cmp: index += 1 nums[index], nums[i] = nums[i], nums[index] return index num_dict = {} for num in nums: if num not in num_dict: num_dict[num] = 1 else: num_dict[num] += 1 # 次数不一定是唯一的 key_dict = {} num_list = [] for j in num_dict: if num_dict[j] not in key_dict: key_dict[num_dict[j]] = [j] else: key_dict[num_dict[j]].append(j) num_list.append(num_dict[j]) index1 = 0 index2 = len(num_list)-1 index = -1 while index != len(num_list)-k: index = quick_partition(num_list, index1, index2) if index < len(num_list)-k: index1 = index + 1 else: index2 = index - 1 choose_num = num_list[index::] out = [] for i in choose_num: out.append(key_dict[i][0]) if len(key_dict[i]) > 1: key_dict[i].pop(0) return out