Comments (2)
上面的优先级队列不完善,如果同优先级的,则应该保持先进先出。需改进 改进思路:
- 堆中的元素和队列有个关系,如k_v={5:queue5,4:queue4}
- 堆每次抛出一个最大值的时候,k_v[5].pop()
- 堆每次添加的时候,kv[5].push("张三")
# -*- coding:utf-8 -*-
#####################################################
# heap 实现
#####################################################
class MaxHeap:
"""
Heaps:
完全二叉树,最大堆的非叶子节点的值都比孩子大,最小堆的非叶子结点的值都比孩子小
Heap包含两个属性,order property 和 shape property(a complete binary tree),在插入
一个新节点的时候,始终要保持这两个属性
插入操作:保持堆属性和完全二叉树属性, sift-up 操作维持堆属性
extract操作:只获取根节点数据,并把树最底层最右节点copy到根节点后,sift-down操作维持堆属性
用数组实现heap,从根节点开始,从上往下从左到右给每个节点编号,则根据完全二叉树的
性质,给定一个节点i, 其父亲和孩子节点的编号分别是:
parent = (i-1) // 2
left = 2 * parent + 1
rgiht = 2 * parent + 2
使用数组实现堆一方面效率更高,节省树节点的内存占用,一方面还可以避免复杂的指针操作,减少
调试难度。
放弃指针操作吧,头晕呜呜呜呜呜呜呜,哭 /-\
"""
def __init__(self, maxsize=32):
self.maxsize = maxsize
self._elements = [None] * self.maxsize
self._count = 0
def __len__(self):
return self._count
def add(self, value):
if self._count >= self.maxsize: # 正常情况下self._count最大下标只有31
raise Exception("full")
self._elements[self._count] = value
self._siftup(self._count)
self._count += 1
def _siftup(self, idx):
if idx > 0:
parent_idx = (idx - 1) // 2
if self._elements[parent_idx] < self._elements[idx]:
self._elements[parent_idx], self._elements[idx] = self._elements[idx], self._elements[parent_idx]
self._siftup(parent_idx)
def extract(self):
value = self._elements[0]
if self._count >= 1:
self._elements[0] = self._elements[self._count - 1]
self._elements[self._count - 1] = None
self._count -= 1
self._siftdown(0)
return value
def _siftdown(self, ndx):
left = 2 * ndx + 1
right = 2 * ndx + 2
# determine which node contains the larger value
largest = ndx
if (right < self._count and # 有右孩子
self._elements[right] >= self._elements[largest] and
self._elements[left] <= self._elements[right]): # 原书这个地方没写实际上找的未必是largest
largest = right
elif left < self._count and self._elements[left] >= self._elements[largest]:
largest = left
if largest != ndx:
self._elements[ndx], self._elements[largest] = self._elements[largest], self._elements[ndx]
self._siftdown(largest)
class PriorityQueue:
def __init__(self):
self._maxheap = MaxHeap()
self.kv = {}
def push(self, key, value):
from collections import deque
# 注意这里把这个 tuple push 进去,python 比较 tuple 从第一个开始比较
# 这样就很巧妙地实现了按照优先级排序
self._maxheap.add(key)
if self.kv.get(key) is None:
deque = deque()
self.kv[key] = deque
self.kv[key].append(value)
def pop(self):
key = self._maxheap.extract()
m = self.kv[key].popleft()
if len(self.kv[key]) == 0:
del self.kv[key]
return m
def is_empty(self):
return len(self._maxheap) == 0
def test_priority_queue():
pq = PriorityQueue()
pq.push(5, 'purple') # key, value
pq.push(0, 'white')
pq.push(3, 'orange')
pq.push(1, 'black')
pq.push(1, 'black1')
res = []
while not pq.is_empty():
res.append(pq.pop())
assert res == ['purple', 'orange', 'black', 'black1', 'white']
if __name__ == '__main__':
test_priority_queue()
```
from python_data_structures_and_algorithms.
建议提一个 mr,使用一个新的类吧,叫做 PrirotyQueueStrict ? 感觉如何呢?保留两个类
from python_data_structures_and_algorithms.
Related Issues (20)
- Hash table 的几个问题 HOT 1
- btree.py里面的preorder_trav_use_stack HOT 1
- 关于Hash的问题 HOT 1
- HashTable里的_find_key() 是有bug,还是我理解有问题 HOT 1
- 关于链表remove 时间复制度问题 HOT 1
- hashtable中的key和value没有解释明白 HOT 1
- 视频能否考虑开源啊? HOT 1
- 你好,关于循环双向链表的remove方法的一些疑问 HOT 2
- 关于您python-web-guide仓库的一个问题 HOT 1
- 堆与堆排序的问题 HOT 1
- 循环双端列表链表append问题
- 单测问题 HOT 2
- linked_list.py的remove方法貌似有误 HOT 1
- 你好,剑指offer33题目的标题和内容不匹配哈,标题是最小数,代码是最大数 HOT 1
- gitbook勘误 HOT 2
- leetcode实战 HOT 1
- 哈希表的二次探测函数有bug,会出现无限循环
- array 可以装别的 class吗? 自定义的class
- 课时6find方法为什么不能和remove那样呢
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from python_data_structures_and_algorithms.