在一个 最小堆 (min heap) 中,如果 P 是 C 的一个父级节点,那么 P 的 key(或 value) 应小于或等于 C 的对应值。 正因为此,堆顶元素一定是最小的,我们会利用这个特点求最小值或者第 k 小的值。
在一个 最大堆 (max heap) 中,P 的 key(或 value) 大于或等于 C 的对应值。
以python为例,说明堆的几个常见操作,这里需要用到一个内置的包:heapq
python中使用堆是通过传入一个数组,然后调用一个函数,在原地让传入的数据具备堆的特性
需要注意的是,heapify默认构造的是小顶堆(min heap),如果要构造大顶堆,思路是把所有的数值倒转,既* -1,例如:
使用heapq提供的函数: heappop 来实现
具体使用方式参考 初始化Heapify
使用heapq提供的函数: heappush 来实现
同时heapq还提供另外一个函数: heappushpop ,能够在一个函数实现push&pop两个操作;顺序是:先push再pop
根据官方文档的描述,这个函数会比先在外围先调用heappush,再调用heappop,效率更高
先pop数据再push数据,和heappushpop的顺序是反着的; 同样的,这样调用的性能也会比先调用heappop再调用heappush更好
如果pop的时候队列是空的,会抛出一个异常
可以通过 heapq.merge 将多个 已排序 的输入合并为一个已排序的输出,这个本质上不是堆;其实就是用两个指针迭代
对于这个问题,有一个算法题可以实现相同的功能
从 iterable 所定义的数据集中返回前 n 个最大/小元素组成的列表。
函数为: heapq.nlargest() | heapq.nsmallest()
heapq - Heap queue algorithm - Python 3.10.4 documentation
python实现堆栈与队列的方法本文实例讲述了python实现堆栈与队列的方法。分享给大家供大家参考。具体分析如下:
1、python实现堆栈,可先将Stack类写入文件stack.py,在其它程序文件中使用from stack import Stack,然后就可以使用堆栈了。
stack.py的程序:
代码如下:class Stack():
def __init__(self,size):
self.size=size
self.stack=[]
self.top=-1
def push(self,ele): #入栈之前检查栈是否已满
if self.isfull():
raise exception("out of range")
else:
self.stack.append(ele)
self.top=self.top+1
def pop(self): # 出栈之前检查栈是否为空
if self.isempty():
raise exception("stack is empty")
else:
self.top=self.top-1
return self.stack.pop()
def isfull(self):
return self.top+1==self.size
def isempty(self):
return self.top==-1
再写一个程序文件,stacktest.py,使用栈,内容如下:
代码如下:#!/usr/bin/python
from stack import Stack
s=Stack(20)
for i in range(3):
s.push(i)
s.pop()
print s.isempty()
2、python 实现队列:
复制代码代码如下:class Queue():
def __init__(self,size):
self.size=size
self.front=-1
self.rear=-1
self.queue=[]
def enqueue(self,ele): #入队操作
if self.isfull():
raise exception("queue is full")
else:
self.queue.append(ele)
self.rear=self.rear+1
def dequeue(self): #出队操作
if self.isempty():
raise exception("queue is empty")
else:
self.front=self.front+1
return self.queue[self.front]
def isfull(self):
return self.rear-self.front+1==self.size
def isempty(self):
return self.front==self.rear
q=Queue(10)
for i in range(3):
q.enqueue(i)
print q.dequeue()
print q.isempty()
希望本文所述对大家的Python程序设计有所帮助。
堆与栈是C/C++语言内存管理和编译优化时使用的。后来JAVA通常只考虑堆,栈偶尔考虑一下。
python与C密切结合。不过大部分时间你都不需要考虑堆与栈。
因为内存超过500MB会变慢。超过2GB,几乎不可能。
栈基本上不用考虑。不过,在递归时,这个短板就出来了。所以在python里,递归层次太多,要改用堆栈,而不能用递归。