Skip to content

Commit 030a498

Browse files
yidao620cyidao620c
committed
priority queue
1 parent dc66467 commit 030a498

3 files changed

Lines changed: 193 additions & 12 deletions

File tree

‎ch02_sort/at014_heapsort.py‎

Lines changed: 26 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -20,25 +20,39 @@
2020
__author__ = 'Xiong Neng'
2121

2222

23-
def heapSort(heap):
23+
class Heap():
24+
def __init__(self, seq, heapSize, length):
25+
"""
26+
seq: 存放待排序的序列
27+
heapSize: 堆的大小
28+
lenght: 整个序列大小
29+
"""
30+
self.seq = seq
31+
self.heapSize = heapSize
32+
self.length = length
33+
34+
35+
def heapSort(seq):
2436
"""
2537
堆排序算法
2638
"""
39+
heap = Heap(seq, len(seq), len(seq))
2740
__buildMaxHeap(heap)
28-
for i in range(heap[2] - 1, 0, -1):
29-
heap[0][0], heap[0][i] = heap[0][i], heap[0][0]
30-
heap[1] -= 1
41+
s = heap.seq
42+
for i in range(heap.length - 1, 0, -1):
43+
s[0], s[i] = s[i], s[0]
44+
heap.heapSize -= 1
3145
__maxHeapify(heap, 0)
3246

3347

3448
def __maxHeapify(heap, i):
3549
"""
3650
前提是i的两棵子树left(i)和right(i)的二叉树都是最大堆了
3751
现在加入i节点后，要保持这个二叉树为最大堆的性质
38-
heap: 一个包含[seq，heapSize，length]的数组
52+
heap: Heap数据结构
3953
"""
40-
seq = heap[0]
41-
slen = heap[1]
54+
seq = heap.seq
55+
slen = heap.heapSize
4256
while True:
4357
left = (i << 1) + 1
4458
right = (i + 1) << 1
@@ -59,15 +73,15 @@ def __buildMaxHeap(heap):
5973
"""
6074
由完全二叉树的性质可知：对于 n/2..n-1为下标的元素，都是叶子节点，
6175
那么可从下标floor((i+1)/2 - 1)开始往前到0的元素调用maxHeapify
62-
heap: 一个包含[seq，heapSize，length]的数组
76+
heap: Heap数据结构
6377
"""
64-
slen = heap[1] = heap[2]
78+
slen = heap.heapSize
6579
for i in range(((slen + 1) >> 1) - 1, -1, -1):
6680
__maxHeapify(heap, i)
6781

6882

6983
if __name__ == '__main__':
70-
h = [[9, 7, 8, 10, 16, 3, 14, 2, 1, 4], 0, 10]
71-
heapSort(h)
72-
print(h[0])
84+
iSeq = [9, 7, 8, 10, 16, 3, 14, 2, 1, 4]
85+
heapSort(iSeq)
86+
print(iSeq)
7387

‎ch02_sort/at015_elevator.py‎

Lines changed: 47 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,47 @@
1+
#!/usr/bin/env python
2+
# -*- encoding: utf-8 -*-
3+
# at015_elevator: 电梯调度算法
4+
"""
5+
Topic: sample
6+
Desc : 电梯调度算法
7+
电梯停在哪一层楼，能够保证这次乘坐电梯的所有乘客爬楼梯的层数之和最少
8+
这个属于动态规划问题
9+
动态规划。假设电梯停在第x层，已知目的楼层
10+
在x层以下的有N1人,
11+
在x层的有N2人，
12+
在x层以上的有N3人。
13+
此时总花费为sum。
14+
则往上走一层的话，总花费变为sum + N2 + N1 - N3。
15+
那么初始状态电梯停在第一层，向上进行状态的变迁，开始时N2 + N1 - N3 < 0。
16+
sum越来越小，直到某一层N2 + N1 >= N3，就没有必要在往上走了。
17+
这时已求出最合适的楼层了
18+
"""
19+
__author__ = 'Xiong Neng'
20+
21+
22+
def elevatorSchedule(seq):
23+
"""
24+
seq: 去往每层的人数， 下标代表楼层号， 很明显0和1层都是0
25+
"""
26+
N1 = N2 = 0 # 到当前层以下的有N1人， 到当前层的有N1人
27+
N3 = 0 # 到当前层以上的有N3人
28+
nMinFloors = 0 # 所有乘客要爬的楼层最小总和
29+
nTargetFloor = 1 # 达到最小值时候的楼层
30+
for i in range(2, len(seq)):
31+
N3 += seq[i]
32+
nMinFloors += seq[i] * (i - 1)
33+
for i in range(2, len(seq)):
34+
if N1 + N2 < N3:
35+
nTargetFloor = i
36+
nMinFloors += (N1 + N2 - N3)
37+
N1 += N2
38+
N2 = seq[i]
39+
N3 -= seq[i]
40+
else:
41+
break
42+
return nTargetFloor, nMinFloors
43+
44+
45+
if __name__ == '__main__':
46+
s = [0, 0, 2, 4, 5, 7, 2, 1]
47+
print(elevatorSchedule(s))

‎ch02_sort/at016_priorqueue.py‎

Lines changed: 120 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,120 @@
1+
#!/usr/bin/env python
2+
# -*- encoding: utf-8 -*-
3+
# at016_priorqueue: 最大堆实现最大优先级队列
4+
"""
5+
Topic: sample
6+
Desc : 最大堆实现最大优先级队列
7+
"""
8+
import at014_heapsort as hsort
9+
10+
__author__ = 'Xiong Neng'
11+
12+
13+
class Item():
14+
def __init__(self, val, key, index=-1):
15+
self.val = val
16+
self.key = key
17+
self.index = index
18+
19+
def __cmp__(self, other):
20+
if self.key > other.key:
21+
return 1
22+
else:
23+
return -1 if self.key < other.key else 0
24+
25+
def __str__(self):
26+
return str((self.val, self.key, self.index))
27+
28+
29+
def heapGetMax(heap):
30+
"""返回最大优先队列中取最大值"""
31+
return heap.seq[0]
32+
33+
34+
def heapPopMax(heap):
35+
"""弹出最大优先队列中取最大值并返回这个值"""
36+
if heap.heapSize < 1:
37+
return None
38+
re = heap.seq[0]
39+
heap.seq[0] = heap.seq[heap.heapSize - 1] # 尾上的弄到头上去
40+
heap.heapSize -= 1 # heap的大小-1
41+
__maxHeapify(heap, 0) # 然后再次将其构建为最大堆
42+
return re
43+
44+
45+
def heapIncreaseKey(heap, item, newKey):
46+
"""增加队列中元素item的key为新的newKey, key <= newKey"""
47+
if newKey < item.key:
48+
return
49+
item.key = newKey
50+
while True:
51+
tmpItem = item
52+
iindex = tmpItem.index
53+
pindex = ((tmpItem.index + 1) >> 1) - 1
54+
if iindex > 0 and heap.seq[pindex] < tmpItem:
55+
heap.seq[iindex], heap.seq[pindex] = heap.seq[pindex], heap.seq[iindex]
56+
heap.seq[iindex].index, heap.seq[pindex].index = iindex, pindex
57+
else:
58+
break
59+
60+
61+
def heapInsert(heap, item):
62+
"""最大优先队列中插入一条元素item，将其放入队列到最后一个位置，
63+
然后调用heapIncreaseKey"""
64+
heap.heapSize += 1
65+
item.index = heap.heapSize - 1
66+
heap.seq[heap.heapSize - 1] = item
67+
heapIncreaseKey(heap, item, item.key)
68+
69+
70+
def __maxHeapify(heap, i):
71+
"""
72+
前提是i的两棵子树left(i)和right(i)的二叉树都是最大堆了
73+
现在加入i节点后，要保持这个二叉树为最大堆的性质
74+
heap: Heap数据结构
75+
"""
76+
seq = heap.seq
77+
slen = heap.heapSize
78+
while True:
79+
left = (i << 1) + 1
80+
right = (i + 1) << 1
81+
if left < slen and seq[left] > seq[i]:
82+
largest = left
83+
else:
84+
largest = i
85+
if right < slen and seq[right] > seq[largest]:
86+
largest = right
87+
if largest != i:
88+
seq[largest], seq[i] = seq[i], seq[largest]
89+
seq[largest].index, seq[i].index = seq[i].index, seq[largest].index
90+
i = largest
91+
else:
92+
break
93+
94+
95+
def __buildMaxHeap(heap):
96+
"""
97+
由完全二叉树的性质可知：对于 n/2..n-1为下标的元素，都是叶子节点，
98+
那么可从下标floor((i+1)/2 - 1)开始往前到0的元素调用maxHeapify
99+
heap: Heap数据结构
100+
"""
101+
slen = heap.heapSize
102+
for i in range(((slen + 1) >> 1) - 1, -1, -1):
103+
__maxHeapify(heap, i)
104+
for i in range(heap.heapSize):
105+
heap.seq[i].index = i
106+
107+
108+
if __name__ == '__main__':
109+
iSeq = [9, 7, 8, 10, 16, 3, 14, 2, 1, 4]
110+
iVal = ['9', '7', '8', '10', '16', '3', '14', '2', '1', '4']
111+
iVal = [2 * k for k in iVal]
112+
pa = zip(iVal, iSeq)
113+
lastParm = [Item(v, k) for (v, k) in pa]
114+
lastParm.extend([None] * 100)
115+
heap = hsort.Heap(lastParm, len(iSeq), len(lastParm))
116+
__buildMaxHeap(heap)
117+
print([str(k) for k in heap.seq if k])
118+
119+
heapInsert(heap, Item('Love', 13))
120+
print([str(k) for k in heap.seq if k])

0 commit comments

Comments
 (0)