|
<div class="markdown-here-wrapper" data-md-url="https://i.cnblogs.com/EditPosts.aspx?postid=10346607">
<h1 id="-" style="margin: 20px 0px 10px; padding: 0px; font-weight: bold; color: black; font-size: 24px; border-bottom: 2px solid #aaaaaa;">优先级队列
<blockquote style="margin: 1.2em 0px; border-left: 4px solid #dddddd; padding: 0px 1em; color: #777777; quotes: none;">
<p style="margin: 0px 0px 1.2em !important; font-size: 16px; line-height: 1.75em; padding-right: 0.5em; padding-left: 0.5em;">如果我们给每个元素都分配一个数字来标记其优先级，不妨设较小的数字具有较高的优先级，这样我们就可以在一个集合中访问优先级最高的元素并对其进行查找和删除操作了。这样，我们就引入了优先级队列 这种数据结构
=2^h-1+1且n<=2^h-1+2^h
=log(n+1)-1
:
<span class="hljs-class"><span class="hljs-keyword" style="font-weight: bold;">class <span class="hljs-title" style="font-weight: bold; color: #0048ab;">HeapPriorityQueue<span class="hljs-params">():
<span class="hljs-string" style="color: #0048ab;">"""
使用堆与列表实现的优先级队列
"""</span>
<span class="hljs-class"><span class="hljs-keyword" style="font-weight: bold;">class</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;">Item</span><span class="hljs-params">()</span>:</span>
<span class="hljs-string" style="color: #0048ab;">"""
队列中的项类
"""</span>
<span class="hljs-function"><span class="hljs-keyword" style="font-weight: bold;">def</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;">__init__</span><span class="hljs-params">(self,key,value)</span>:</span>
self.key = key
self.value = value
<span class="hljs-function"><span class="hljs-keyword" style="font-weight: bold;">def</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;">__it__</span><span class="hljs-params">(self,other)</span>:</span>
<span class="hljs-keyword" style="font-weight: bold;">return</span> self.key < other.key
<span class="hljs-function"><span class="hljs-keyword" style="font-weight: bold;">def</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;">is_empty</span><span class="hljs-params">(self)</span>:</span>
<span class="hljs-keyword" style="font-weight: bold;">return</span> len(self) == <span class="hljs-number">0</span>
<span class="hljs-function"><span class="hljs-keyword" style="font-weight: bold;">def</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;">parent</span><span class="hljs-params">(self,j)</span>:</span>
<span class="hljs-string" style="color: #0048ab;">"""
返回父节点的索引
"""</span>
<span class="hljs-keyword" style="font-weight: bold;">return</span> (j - <span class="hljs-number">1</span>) // <span class="hljs-number">2</span>
<span class="hljs-function"><span class="hljs-keyword" style="font-weight: bold;">def</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;">left</span><span class="hljs-params">(self,j)</span>:</span>
<span class="hljs-string" style="color: #0048ab;">"""返回左孩子索引"""</span>
<span class="hljs-keyword" style="font-weight: bold;">return</span> <span class="hljs-number">2</span> * j + <span class="hljs-number">1</span>
<span class="hljs-function"><span class="hljs-keyword" style="font-weight: bold;">def</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;">right</span><span class="hljs-params">(self,j)</span>:</span>
<span class="hljs-string" style="color: #0048ab;">"""返回右孩子索引"""</span>
<span class="hljs-keyword" style="font-weight: bold;">return</span> <span class="hljs-number">2</span> * j + <span class="hljs-number">2</span>
<span class="hljs-function"><span class="hljs-keyword" style="font-weight: bold;">def</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;">has_left</span><span class="hljs-params">(self,j)</span>:</span>
<span class="hljs-string" style="color: #0048ab;">"""通过判断索引是否出了列表来判断是否存在"""</span>
<span class="hljs-keyword" style="font-weight: bold;">return</span> self.left(j) < len(self.data)
<span class="hljs-function"><span class="hljs-keyword" style="font-weight: bold;">def</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;">has_right</span><span class="hljs-params">(self,j)</span>:</span>
<span class="hljs-keyword" style="font-weight: bold;">return</span> self.right(j) < len(self.data)
<span class="hljs-function"><span class="hljs-keyword" style="font-weight: bold;">def</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;">swap</span><span class="hljs-params">(self,i,j)</span>:</span>
self.data[i],self.data[j] = self.data[j],self.data[i]
<span class="hljs-function"><span class="hljs-keyword" style="font-weight: bold;">def</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;">upheap</span><span class="hljs-params">(self,j)</span>:</span>
<span class="hljs-string" style="color: #0048ab;">"""向上堆排序"""</span>
parent = self.parent(j)
<span class="hljs-keyword" style="font-weight: bold;">if</span> j > <span class="hljs-number">0</span> <span class="hljs-keyword" style="font-weight: bold;">and</span> self.data[j] < self.data[parent]:
self.swap(j,parent)
self.upheap(parent)
<span class="hljs-function"><span class="hljs-keyword" style="font-weight: bold;">def</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;">downheap</span><span class="hljs-params">(self,j)</span>:</span>
<span class="hljs-string" style="color: #0048ab;">"""向下堆排序"""</span>
<span class="hljs-keyword" style="font-weight: bold;">if</span> self.has_left(j):
left = self.left(j)
small = left
<span class="hljs-keyword" style="font-weight: bold;">if</span> self.has_right(j):
right = self.right(j)
<span class="hljs-keyword" style="font-weight: bold;">if</span> self.data[right] < self.data[left]:
small = right
<span class="hljs-keyword" style="font-weight: bold;">if</span> self.data[small] < self.data[j]:
self.swap(small,j)
self.downheap(small)
<span class="hljs-function"><span class="hljs-keyword" style="font-weight: bold;">def</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;">__init__</span><span class="hljs-params">(self)</span>:</span>
self.data = []
<span class="hljs-function"><span class="hljs-keyword" style="font-weight: bold;">def</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;">__len__</span><span class="hljs-params">(self)</span>:</span>
<span class="hljs-keyword" style="font-weight: bold;">return</span> len(self.data)
<span class="hljs-function"><span class="hljs-keyword" style="font-weight: bold;">def</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;">add</span><span class="hljs-params">(self,value)</span>:</span>
<span class="hljs-string" style="color: #0048ab;">"""添加一个元素，并进行向上堆排序"""</span>
self.data.append(self.Item(key,value))
self.upheap(len(self.data) - <span class="hljs-number">1</span>)
<span class="hljs-function"><span class="hljs-keyword" style="font-weight: bold;">def</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;">min</span><span class="hljs-params">(self)</span>:</span>
<span class="hljs-keyword" style="font-weight: bold;">if</span> self.is_empty():
<span class="hljs-keyword" style="font-weight: bold;">raise</span> Empty(<span class="hljs-string" style="color: #0048ab;">'Priority queue is empty'</span>)
item = self.data[<span class="hljs-number">0</span>]
<span class="hljs-keyword" style="font-weight: bold;">return</span> (item.key,item.value)
<span class="hljs-function"><span class="hljs-keyword" style="font-weight: bold;">def</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;">remove_min</span><span class="hljs-params">(self)</span>:</span>
<span class="hljs-keyword" style="font-weight: bold;">if</span> self.is_empty():
<span class="hljs-keyword" style="font-weight: bold;">raise</span> Empty(<span class="hljs-string" style="color: #0048ab;">'Priority queue is empty'</span>)
self.swap(<span class="hljs-number">0</span>,len(self.data) - <span class="hljs-number">1</span>)
item = self.data.pop()
self.downheap(<span class="hljs-number">0</span>)
<span class="hljs-keyword" style="font-weight: bold;">return</span> (item.key,item.value)
<h1 id="python-heapq-" style="margin: 20px 0px 10px; padding: 0px; font-weight: bold; color: black; font-size: 24px; border-bottom: 2px solid #aaaaaa;">python的heapq模块
<p style="margin: 0px 0px 1.2em !important; font-size: 16px; line-height: 1.75em; padding-right: 0.5em; padding-left: 0.5em;">Python标准包含了heapq模块，但他并不是一个独立的数据结构，而是提供了一些函数，这些函数吧列表当做堆进行管理,而且元素的优先级就是列表中的元素本身,除此之外它的模型与实现方式与刚才我们自己定义的基本相同
<p style="margin: 0px 0px 1.2em !important; font-size: 16px; line-height: 1.75em; padding-right: 0.5em; padding-left: 0.5em;">有以下函数：
<ul style="margin: 1.2em 0px; padding-left: 2em; list-style-type: square; font-size: 16px;">
<li style="margin: 0.5em 0px; font-size: 16px;">
<p style="margin: 0.5em 0px !important; font-size: 16px; line-height: 1.75em; padding-right: 0.5em; padding-left: 0.5em;">heappush(L,e): 将元素e存入列表L中并进行堆排序
（编辑：李大同）
【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!
|
