机试——堆相关的问题

堆相关知识

​ 堆是一种特殊的完全二叉树，其父节点的值都比子节点的大(大根堆)，

注意：堆的孩子节点左右无大小关系

相关知识：

完全二叉树

​ 性质：1.完全二叉树的深度为logn

​ 2.最后一个非叶子节点为n//2

​ 3.一个编号为x的节点父节点的编号为x//2

​ 4.一个编号为x的左孩子节点为2*x

​ 完全二叉树一般都存储在数组中，但是由于二叉树节点的序号是从1开始的，数组索引是从0开始的，所以需要将恰其全部向后移动一位，将索引为0的位空出来，从1开始计数，但是在python中数组因为没有appendleft方法，因此一般采用colllections中的deque链表类来进行存储(因为其有appendleft方法，直接在首位添加空位)

from collections import deque
L = deque([50, 16, 30, 10, 60,  90,  2, 80, 70])
L.appendleft(0)

​

堆操作

​ 性质：1.插入新元素的时间复杂度为logn，比较次数就是完全二叉树的深度

插入元素

​ 直接将新元素插入到末尾，再根据情况判断新元素是否需要上移，直到满足堆的特性为止。如果堆的大小为N（即有N个元素），那么插入一个新元素所需要的时间也是O(logN)。

​ 下面以在小根堆中插入新节点为例：

heap.append(i)

def insert_heapq(i):
	flag = 0   #标志是否还需要进行向上调整
  if i==1:
    return 
  while i!=1 and flag==0:
    if heap[i]<heap[i//2]:
      heap[i],heap[i//2] = heap[i//2],heap[i]
      
   	else:
      flag = 1
   	i = i//2

建立堆

​ 建立堆最自然的思路就是从空的堆开始不断向堆中添加元素，直到所有数据都被插入堆中，此时由于插入每个元素的时间复杂度为O(logi)，所以插入全部数据的时间复杂度为O(nlogn)

​ 而真正的堆建立往往采取另外一种更加高效的时间复杂度为O(n)的方法来进行，即直接先将全部数放入完全二叉树,然后在这个棵完全二叉树中，我们从最后一个结点开始依次判断以这个结点为根的子树是否符合最小堆的特性。如果所有的子树都符合最小堆的特性，那么整棵树就是最小堆了。

​ 具体做法如下：

​ 首先我们从叶结点开始。因为叶结点没有儿子，所以所有以叶结点为根结点的子树（其实这个子树只有一个结点）都符合最小堆的特性（即父结点的值比子结点的值小）。这些叶结点压根就没有子节点，当然符合这个特性。因此所有叶结点都不需要处理，直接跳过。从第n/2个结点开始（n为完全二叉树的结点总数，这里即7号结点）处理这棵完全二叉树。（这里用到了完全二叉树的性质：最后一个非叶结点是第n/2个结点)。

#调整编号为n的节点符合堆结构(这里是最小堆)
def head_adjust(i,end):
  tmp = L[i]
 
  j = i*2  #j是i的左子节点索引
  while j<=end:
    if j<end and heap[j]>heap[j+1]:
      j = j+1      #这里是比较两个孩子，将比较小的索引付给j
    if heap[j]<heap[i]:     #比较该节点和孩子中比较小的，如该节点比孩子中比较小的大，那么交换两个节点
      heap[i],heap[j] = heap[j],heap[i]
      i = j
      j *= i
    else:     #如果比孩子中较小的还小，说明一符合堆特性，不必继续向下遍历
      break     #由于是自下向上的，如果该节点移到的位置已经比两个子节点都小，那么他们也一定比孩子的孩子小

#从一个列表创建一个堆
def create_heap(L):
	from collections import deque
  heap =deque(L)
	heap.appendleft(0)
  
 	length = len(heap)-1
  last_no_leaf_index = length//2
  for i in range(last_no_leaf_index):
    heap_adjust(last_no_leaf_index-i,length)

堆排序

​ 平均时间复杂度：O(nlogn)

​ 最坏时间复杂度：O(nlogn)

时间复杂度主要是由于建立好堆后输出排序时，每输出一个结果要将一个数据从头向下比较，时间为O(logn)，有n次比较，因此总的时间复杂度为O(nlogn)

​ 堆排序的核心思想如下：

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

​ 这里第一步就是小根堆的建立过程，上面已经有了，不在赘述，下面是第二、三不断交换完成啊排序的过程：

for i in range(length-1):
  heap[i],heap[length-i] = heap[length-i],heap[i]
  heap_adjust(i,length-i)    #每次都会有一个元素相当于已经输出，从后向前依次
  result = [L[i] for i in range(1,length+1)]
  return result

​ 因此整个堆排序过程为:

#调整编号为n的节点符合堆结构(这里是最小堆)
def head_adjust(i,end):
  tmp = L[i]
 
  j = i*2  #j是i的左子节点索引
  while j<=end:
    if j<end and heap[j]>heap[j+1]:
      j = j+1      #这里是比较两个孩子，将比较小的索引付给j
    if heap[j]<heap[i]:     #比较该节点和孩子中比较小的，如该节点比孩子中比较小的大，那么交换两个节点
      heap[i],heap[j] = heap[j],heap[i]
      i = j
      j *= i
    else:     #如果比孩子中较小的还小，说明一符合堆特性，不必继续向下遍历
      break     #由于是自下向上的，如果该节点移到的位置已经比两个子节点都小，那么他们也一定比孩子的孩子小

#从一个列表创建一个堆
def heap_sort(L):
  #创建堆
	from collections import deque
  heap =deque(L)
	heap.appendleft(0)
  
 	length = len(heap)-1
  last_no_leaf_index = length//2
  for i in range(last_no_leaf_index):
    heap_adjust(last_no_leaf_index-i,length)

  #输出堆的各个元素
  for i in range(length-1):
    heap[i],heap[length-i] = heap[length-i],heap[i]
    heap_adjust(i,length-i)    #每次都会有一个元素相当于已经输出，从后向前依次
    result = [L[i] for i in range(1,length+1)]
  return result

python中内置的堆

​ python中只内置了小根堆，要使用大根堆的功能，可以将数转化成对应的负值进行堆操作，出堆时再取负值即为原来的最大值

python中的堆引用：

import heapq

常用方法：

1.heapq.heapify(list) 将一个列表、元组穿换成小根堆对象，后续可以直接用堆操作

2.heapq.heappop(heap) 将堆顶元素出堆

堆常见题目

1.前K个高频的单词

给一非空的单词列表，返回前 k 个出现次数最多的单词。

返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率，按字母顺序排序。

示例 1：

输入: ["i", "love", "leetcode", "i", "love", "coding"], k = 2
输出: ["i", "love"]
解析: "i" 和 "love" 为出现次数最多的两个单词，均为2次。
    注意，按字母顺序 "i" 在 "love" 之前。

示例 2：

输入: ["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"], k = 4
输出: ["the", "is", "sunny", "day"]
解析: "the", "is", "sunny" 和 "day" 是出现次数最多的四个单词，
    出现次数依次为 4, 3, 2 和 1 次。

分析：本题的主要难点在出现频率相同的但此处理上

解法一：利用Counter进行排序

关键点：使用Couner进行词频统计后如何进行排序，这里的排序只能使用频率的负值和首字母进行升序排序。为什么仔细进行思考，例:[“i”, “love”, “leetcode”, “i”, “love”, “coding”]

def topKFrequent(self, words: List[str], k: int) -> List[str]:
        from collections  import Counter
        result = []
        word_list = list(Counter(words).most_common())
        word_list = sorted(word_list,key=lambda x:[-x[1],x[0]])  #这里的排序使用只能使用频率的负值进行排序和首字母进行升序排序
        for i in range(k):
            result.append(word_list[i][0])
        
        return result

解法二：使用headp进行堆排序

def topKFrequent(self, words: List[str], k: int) -> List[str]:
         
        import collections
        count = collections.Counter(nums)
        heap = [(-freq, word) for word, freq in count.items()]
        import heapq
        heapq.heapify(heap)
        return [heapq.heappop(heap)[1] for _ in range(k)]