脚本宝典收集整理的这篇文章主要介绍了1.1.5 堆Heap,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
实现最小堆:
实现最大堆:将元素取反存入堆,取出时再取反:将push(e)改为push(-e)、pop(e)改为-pop(e)。
又被为优先队列(priority queue)。尽管名为优先队列,但堆并不是队列。回忆一下,在队列中,我们可以进行的限定操作是dequeue和enqueue。
dequeue是按照进入队列的先后顺序来取出元素。而在堆中,我们不是按照元素进入队列的先后顺序取出元素的,而是按照元素的优先级取出元素。
堆的实现通过构造二叉堆(binary heap),实为二叉树的一种;由于其应用的普遍性,当不加限定时,均指该数据结构的这种实现。这种数据结构具有以下性质。
上浮(Promotion)
情境: 子节点的键值变为比父节点的键值大;如下面添加字节点
消除这种违反项:
堆的添加:
def _upheap(self, j):#往上交换
parent = self._parent(j)
if j > 0 and self._data[j] < self._data[parent]:
self._swap(j, parent)
self._upheap(parent)
下沉(Demotion)
情境:父节点的键值变得比子节点(一个或者2个) 的键值还小 ,如下面删除了根节点后拿了个小子节点补充上来的情况
消除这种违反项:
删除最大值
def _downheap(self, j):#往下交换,递归比较三个值
if self._has_left(j):
left = self._left(j)
small_child = left
if self._has_right(j):
right = self._right(j)
if self._data[right] < self._data[left]:
small_child = right
if self._data[small_child] < self._data[j]:
self._swap(j, small_child)
self._downheap(small_child)
@H_896_126@
构建堆的代码:
#该heap为min_heap,即根节点为最小值
class PriorityQueueBase:
#抽象基类为堆
class Item:
#轻量级组合来存储堆项目
__slots__ = '_key' , '_value'
def __init__ (self, k, v):
self._key = k
self._value = v
def __lt__ (self, other): #比较大小
return self._key < other._key
def is_empty(self):
return len(self) == 0
def __str__(self):
return str(self._key)
class HeapPriorityQueue(PriorityQueueBase):
def __init__ (self):
self._data = [ ]
def __len__ (self):
return len(self._data)
def is_empty(self):
return len(self) == 0
def add(self, key, value): #在后面加上然后加上
self._data.apPEnd(self.Item(key, value))
self._upheap(len(self._data) - 1)
def min(self):
if self.is_empty():
raise ValueError( "Priority queue is empty." )
item = self._data[0]
return (item._key, item._value)
def remove_min(self):
if self.is_empty():
raise ValueError( "Priority queue is empty." )
self._swap(0, len(self._data) - 1)
item = self._data.pop( )
self._downheap(0)
return (item._key, item._value)
def _parent(self, j):
return (j - 1) // 2
def _left(self, j):
return 2 * j + 1
def _right(self, j):
return 2 * j + 2
def _has_left(self, j):
return self._left(j) < len(self._data)
def _has_right(self, j):
return self._right(j) < len(self._data)
def _swap(self, i, j):
self._data[i], self._data[j] = self._data[j], self._data[i]
def _upheap(self, j):#往上交换
parent = self._parent(j)
if j > 0 and self._data[j] < self._data[parent]:
self._swap(j, parent)
self._upheap(parent)
def _downheap(self, j):#往下交换,递归比较三个值
if self._has_left(j):
left = self._left(j)
small_child = left
if self._has_right(j):
right = self._right(j)
if self._data[right] < self._data[left]:
small_child = right
if self._data[small_child] < self._data[j]:
self._swap(j, small_child)
self._downheap(small_child)
heap = HeapPriorityQueue()
heap.add(4, "D")
heap.add(3, "C")
heap.add(1, "A")
heap.add(5, "E")
heap.add(2, "B")
heap.add(7, "G")
heap.add(6, "F")
heap.add(26, "Z")
for item in heap._data:
print(item)
print("min is: ")
print(heap.min())
print()
print("remove min: ")
print(heap.remove_min())
print("Now min is: ")
print(heap.min())
print()
print("remove min: ")
print(heap.remove_min())
print("Now min is: ")
print(heap.min())
print()
heap.add(1, "A")
print("Now min is: ")
print(heap.min())
print()
#输出结果
1
2
3
5
4
7
6
26
min is:
(1, 'A')
remove min:
(1, 'A')
Now min is:
(2, 'B')
remove min:
(2, 'B')
Now min is:
(3, 'C')
Now min is:
(1, 'A')
python内置方法创建堆有两种方式,heappush()和heapify():
'''
heaqp模块提供了堆队列算法的实现,也称为优先级队列算法。
要创建堆,请使用初始化为[]的列表,或者可以通过函数heapify()将填充列表转换为堆。
提供以下功能:
heapq.heappush(堆,项目)
将值项推入堆中,保持堆不变。
heapq.heapify(x)
在线性时间内将列表x转换为堆。
heapq.heappop(堆)
弹出并返回堆中的最小项,保持堆不变。如果堆是空的,则引发IndexError。
'''
import heapq #1 heappush生成堆+ heappop把堆从小到大pop出来
heap = []
data = [1,3,5,7,9,2,4,6,8,0]
for i in data:
heapq.heappush(heap,i)
print(heap) lis = []
while heap:
lis.append(heapq.heappop(heap))
print(lis) #2 heapify生成堆+ heappop把堆从小到大pop出来
data2 = [1,5,3,2,9,5]
heapq.heapify(data2)
print(data2) lis2 = []
while data2:
lis2.append(heapq.heappop(data2))
print(lis2) #输出结果
[0, 1, 2, 6, 3, 5, 4, 7, 8, 9]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 2, 3, 5, 9, 5]
[1, 2, 3, 5, 5, 9]
以上是脚本宝典为你收集整理的1.1.5 堆Heap全部内容,希望文章能够帮你解决1.1.5 堆Heap所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。