数据结构与算法06-算法刷题-队列-堆部分

和栈相似,队列也是一种依赖顺序的数据结构,不过它的规则是先进先出(FIFO),在这个基础上会有很多新的操作,和单调栈相似的单调队列、以及不同优先级的基于堆的优先队列方法

0x01 队列的基础知识

队列Queue:是一种线性表数据结构,是一种只允许在表的一端进行插入操作,而在表的另外一端进行删除操作的线性表

队尾(rear):队列中允许插入一端

队头(front):允许删除的另一端

当表中没有任何可操作的数据元素称为空队

同样的队列的设计包括顺序存储的队列和链式存储的队列

队列这种数据结构的基本操作可以分为:

  1. 初始化队列init,定义队列的大小size、队头元素指针front、队尾元素rear
  2. 判断队列是否为空is_empty
  3. 判断队列是否已满,is_ful
  4. 插入元素(入队)
  5. 删除元素(出队)
  6. 获取队列队头元素

0x02 队列的基本设计

T 622 设计循环列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
class MyCircularQueue:

def __init__(self, k: int):
self.size=k
self.queue=[None for _ in range(k)]
self.front=-1
self.rear=-1
self.num=0


def enQueue(self, value: int) -> bool:

if self.isFull():
return False
else:
self.num+=1
self.rear=(self.rear+1)%self.size
self.queue[self.rear]=value
return True


def deQueue(self) -> bool:
if self.isEmpty():
return False
else:
self.num-=1
self.front=(self.front+1)%self.size
return True


def Front(self) -> int:

if self.isEmpty():
return -1
else:
return self.queue[(self.front+1)%self.size]



def Rear(self) -> int:
if self.isEmpty():
return -1
else:
return self.queue[self.rear]


def isEmpty(self) -> bool:
if self.num==0:
return True
else:
return False


def isFull(self) -> bool:
if self.num==self.size:
return True
else:
return False

T 239 滑动窗口最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
stack=[]
# stack用来存储最大值的下标,使用单调递减栈【3,2,1】
arr=[]
for i in range(len(nums)):
# 需要遍历每个数组
# 优先考虑index超出范围的,第i个数的时候,边界局势i-k+1
while stack and stack[0]<i-k+1:
stack.pop(0)
# 之后考虑值的大小
while stack and nums[stack[-1]]<nums[i]:
stack.pop()
stack.append(i)
arr.append(nums[stack[0]])

return arr[k-1:]

0x03 优先队列

队列的作用十分有限,常见的是优先队列,是一种特殊的队列,在优先队列中元素被赋予不同的优先级,当访问队列元素时,按照具有高优先级的元素最先删除;优先对立与普通队列最大的不同点在于出队顺序,优先队列按照优先级来实现 最高级先出的规则

ps:个人认为,和单调栈类似,优先队列的重点在于“优先”,也就是找到一种数据方式,每次插入和删除的时候可以保证最上面一层是自己想的

优先队列的应用场景非常多:

  1. 数据压缩的 huffman编码
  2. 最短路径算法 Dijkstra
  3. 最小生成树算法 prim算法
  4. 任务调度器 根据优先级执行系统任务
  5. 事件驱动仿真 顾客排队算法
  6. 选择问题 查找第K最小元素

0x04 优先队列设计和使用

设计优先级队列,设计的操作主要在于和普通队列的enqueue和dequeue之间的不同

队列的实现方式也不同,可以使用数组实现、链表实现和二叉队实现

  1. 数组实现优先队列,入队操作直接插入rear(O1)、出队操作需要遍历整个数组,找到优先级最高的元素,返回并删除该元素,时间复杂对为O(n)
  2. 链表实现优先队列,链表中的元素按照优先级排序,入队操作需要为待插入元素创建节点,并在链表中找合适的插入位置,时间复杂度为ON
  3. 二叉堆结构实现优先队列,按照优先级进行排序,入队操作就是将元素插入二叉堆中合适位置,时间复杂对为logN、出队操作就是返回二叉堆中优先级最大节点删除,时间复杂度也是O(logN)

当然除了这种笨拙的利用原始数据生成优先队列的方式之外,别人已经写好了轮子,比如java里面的priority Queue、C++的priority queue和python的heapq

4.1 什么是堆?

IMG_56E0A06B6165-1

4.2 堆排序

我们知道小顶堆的特点是堆顶永远是最小的数,虽然我们不知道其他顺序,但是我们知道堆顶是最小的,所以我们可以使用堆数据结构来排序,每次取出最小的,来实现排序。

对于输入的nums数组,我们调用buildMinHeap来实现数组向小顶堆的转变,具体过程是不断调整数组。

在建立小顶堆之后,我们每次取出堆顶元素到数组尾部,并对前面的【0:n-2】进行堆调整,由此来保持堆的特性(这里的heapfiy就是heap Adjust)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
def sortArray(nums):
def heapfiy(arr,index,end):
# 调整成为大顶堆
left=index*2+1
right=left+1
while left<=end:
min_index=index
if arr[left]<arr[min_index]:
min_index=left
if right<=end and arr[right]<arr[min_index]:
min_index=right
if index == min_index:
break

arr[index],arr[min_index]=arr[min_index],arr[index]


# break
index=min_index
left=index*2+1
right=left+1

def buildMinHeap(arr):
size=len(arr)
# 堆里面最重要的一个性质就是,子节点的下标等于i*2+1、i*2+2
# 最后一个非叶节点(size-2)//2
for i in range((size-2)//2,-1,-1):
heapfiy(arr,i,size-1)
return arr

def minHeapSort(arr):
# 原始序列构建大顶堆
# 交换最大值和n-1的顺序
# 新的序列重新构建大顶堆
arr=buildMinHeap(arr)
print(arr)
size=len(arr)
for i in range(size):
arr[0],arr[size-i-1]=arr[size-i-1],arr[0]
heapfiy(arr,0,size-i-2)
return arr

return minHeapSort(nums)
print(sortArray([23,34,23,1,3,9,667,9,0]))

4.3 基于堆实现优先队列

我们知道优先队列是分为两个部分的,一个是优先级、一个是原始数据;因此我们通常需要用堆来存储原始数据,但是在调整的过程中利用优先级来比较。(和单调栈中数据的值和数据的下标类似)

T703 数据流中的第K大元素

很经典就是维护一个长度为k的优先队列,如果数据长了就pop出堆顶元素来保持保持自身的完整性

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
class KthLargest:
# 重点在于是否可以利用add之前数据排列方式

def __init__(self, k: int, nums: List[int]):
self.k=k
self.arr=nums
self.buildHeap(self.k)
while len(self.arr)>self.k:
self.heapPop()
# 维护一个大小的为k的最小堆

def add(self, val: int) -> int:
self.heapPush(val)

while len(self.arr)>self.k:
self.heapPop()
return self.arr[0]

def buildHeap(self,k):
size=len(self.arr)
for i in range((size-2)//2,-1,-1):
# 自下往上的维护一个堆
self.heapAdjust(i,size-1)

def heapAdjust(self,index,end):
# index代表是父节点
child_l=index*2+1
child_r=child_l+1
while(child_l<=end):
min_index=index
if self.arr[child_l]<self.arr[min_index]:
min_index=child_l
if child_r <=end and self.arr[child_r]<self.arr[min_index]:
min_index=child_r
if index==min_index:
break

self.arr[min_index],self.arr[index]=self.arr[index],self.arr[min_index]
index=min_index
child_l=index*2+1
child_r=child_l+1
def heapPop(self):
size=len(self.arr)
self.arr[0],self.arr[-1]=self.arr[-1],self.arr[0]
top=self.arr.pop()
# 重新整理
if size>0:
self.heapAdjust(0,size-2)
return top

def heapPush(self,val):
self.arr.append(val)
size=len(self.arr)
i=size-1
cur_root=(i-1)//2
while(cur_root>=0):
if self.arr[cur_root]<val:
break
self.arr[i]=self.arr[cur_root]
i=cur_root
cur_root=(i-1)//2
self.arr[i]=val

T347 前K个高频元素

这里与之前类似的地方,还是求K个满足条件的值,只不过不是值本身,而是涉及值的元素,所以可以说是堆,也可以说是优先队列,只不过代表的实际值需要翻译一下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
num_dict=dict()
for num in nums:
if num in num_dict:
num_dict[num]+=1
else:
num_dict[num]=1

new_nums=list(set(nums))

def heapfiy(heap,index,end):
child_l=index*2+1
child_r=index*2+2
while(child_l<=end):
min_index=index
if num_dict[heap[min_index]]>num_dict[heap[child_l]]:
min_index=child_l
if child_r<=end and num_dict[heap[min_index]]>num_dict[heap[child_r]]:
min_index=child_r
if num_dict[heap[index]]==num_dict[heap[min_index]]:
break

# 交换堆里面的位置
heap[min_index],heap[index]=heap[index],heap[min_index]
index=min_index
child_l=index*2+1
child_r=index*2+2

def heappush(heap,val):
heap.append(val)
i=len(heap)-1
while((i-1)//2>=0):
cur_root=(i-1)//2
if num_dict[heap[cur_root]]<num_dict[val]:
break
heap[i]=heap[cur_root]
i=cur_root
heap[i]=val
return heap

def heappop(heap):
heap[0],heap[-1]=heap[-1],heap[0]
heap.pop()
heap=heapfiy(heap,0,len(heap)-1)
return heap

# 维护一个堆,每次push一个元素
# 长度超过k,需要pop一个元素
# 需要维护的是最小堆

res=[]
for num in new_nums:
heappush(res,num)

while(len(res)>k):
heappop(res)
return res

T973 最接近原点的K个点

一样的,只不过计数变成了欧氏距离,有点无聊的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Solution:
def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
def disCounting(point):
return point[0]*point[0]+point[1]*point[1]

def heapAdjust(heap,index,end):
child_l=index*2+1
child_r=index*2+2
while(child_l<=end):
max_index=index
if disCounting(heap[child_l])>disCounting(heap[max_index]):
max_index=child_l
if child_r<=end and disCounting(heap[child_r])>disCounting(heap[max_index]):
max_index=child_r
if max_index==index:
break

heap[index],heap[max_index]=heap[max_index],heap[index]
index=max_index
child_l=index*2+1
child_r=index*2+2

def heappush(heap,val):
# 距离为优先级
# 里面的元素为point
heap.append(val)
i=len(heap)-1
while((i-1)//2>=0):
cur_root=(i-1)//2

if disCounting(heap[cur_root])>disCounting(val):
break
heap[i]=heap[cur_root]
i=cur_root
heap[i]=val

def heappop(heap):
heap[0],heap[-1]=heap[-1],heap[0]
heap.pop()
heapAdjust(heap,0,len(heap)-1)

res=[]
for point in points:
heappush(res,point)

while(len(res)>k):
heappop(res)

return res


数据结构与算法06-算法刷题-队列-堆部分
https://blog.tjdata.site/posts/1bbb5318.html
作者
chenxia
发布于
2022年7月13日
许可协议