Python高级数据结构——堆

Python06

Python高级数据结构——堆,第1张

在一个 最小堆 (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由荷兰数学和计算机科学研究学会的Guido van Rossum于1990 年代初设计,作为一门叫做ABC语言的替代品。Python提供了高效的高级数据结构,还能简单有效地面向对象编程。

Python语法和动态类型,以及解释型语言的本质,使它成为多数平台上写脚本和快速开发应用的编程语言,随着版本的不断更新和语言新功能的添加,逐渐被用于独立的、大型项目的开发。

服务器

在你进行CGI编程前,确保您的Web服务器支持CGI及已经配置了CGI的处理程序。

所有的HTTP服务器执行CGI程序都保存在一个预先配置的目录。这个目录被称为CGI目录,并按照惯例,它被命名为/var/www/cgi-bin目录。

CGI文件的扩展名为.cgi,python也可以使用.py扩展名。

默认情况下,Linux服务器配置运行的cgi-bin目录中为/var/www。