python计算最大优先级队列实例
代码如下:
# -*- coding: utf-8 -*-
class Heap(object):
@classmethod
def parent(cls, i):
"""父结点下标"""
return int((i - 1) >> 1);
@classmethod
def left(cls, i):
"""左儿子下标"""
return (i
@classmethod
def right(cls, i):
"""右儿子下标"""
return (i
class MaxPriorityQueue(list, Heap):
@classmethod
def max_heapify(cls, A, i, heap_size):
"""最大堆化A[i]为根的子树"""
l, r = cls.left(i), cls.right(i)
if l A[i]:
largest = l
else:
largest = i
if r A[largest]:
largest = r
if largest != i:
A[i], A[largest] = A[largest], A[i]
cls.max_heapify(A, largest, heap_size)
def maximum(self):
"""返回最大元素,伪码如下:
HEAP-MAXIMUM(S)
1 return A[1]
T(n) = O(1)
"""
return self[0]
def extract_max(self):
"""去除并返回最大元素,伪码如下:
HEAP-EXTRACT-MAX(A)
1 if heap-size[A] 2 then error "heap underflow"
3 max ← A[1]
4 A[1] ← A[heap-size[A]] // 尾元素放到第一位
5 heap-size[A] ← heap-size[A] - 1 // 减小heap-size[A]
6 MAX-HEAPIFY(A, 1) // 保持最大堆性质
7 return max
T(n) = θ(lgn)
"""
heap_size = len(self)
assert heap_size > 0, "heap underflow"
val = self[0]
tail = heap_size - 1
self[0] = self[tail]
self.max_heapify(self, 0, tail)
self.pop(tail)
return val
def increase_key(self, i, key):
"""将i处的值增加到key,伪码如下:
HEAP-INCREASE-KEY(A, i, key)
1 if key 2 the error "new key is smaller than current key"
3 A[i] ← key
4 while i > 1 and A[PARENT(i)] 5 do exchange A[i] ↔ A[PARENT(i)] // 交换两元素
6 i ← PARENT(i) // 指向父结点位置
T(n) = θ(lgn)
"""
val = self[i]
assert key >= val, "new key is smaller than current key"
self[i] = key
parent = self.parent
while i > 0 and self[parent(i)] self[i], self[parent(i)] = self[parent(i)], self[i]
i = parent(i)
def insert(self, key):
"""将key插入A,伪码如下:
MAX-HEAP-INSERT(A, key)
1 heap-size[A] ← heap-size[A] + 1 // 对元素个数增加
2 A[heap-size[A]] ← -∞ // 初始新增加元素为-∞
3 HEAP-INCREASE-KEY(A, heap-size[A], key) // 将新增元素增加到key
T(n) = θ(lgn)
"""
self.append(float('-inf'))
self.increase_key(len(self) - 1, key)
if __name__ == '__main__':
import random
keys = range(10)
random.shuffle(keys)
print(keys)
queue = MaxPriorityQueue() # 插入方式建最大堆
for i in keys:
queue.insert(i)
print(queue)
print('*' * 30)
for i in range(len(keys)):
val = i % 3
if val == 0:
val = queue.extract_max() # 去除并返回最大元素
elif val == 1:
val = queue.maximum() # 返回最大元素
else:
val = queue[1] + 10
queue.increase_key(1, val) # queue[1]增加10
print(queue, val)
print([queue.extract_max() for i in range(len(queue))])

Hot AI Tools

Undresser.AI Undress
AI-powered app for creating realistic nude photos

AI Clothes Remover
Online AI tool for removing clothes from photos.

Undress AI Tool
Undress images for free

Clothoff.io
AI clothes remover

AI Hentai Generator
Generate AI Hentai for free.

Hot Article

Hot Tools

Notepad++7.3.1
Easy-to-use and free code editor

SublimeText3 Chinese version
Chinese version, very easy to use

Zend Studio 13.0.1
Powerful PHP integrated development environment

Dreamweaver CS6
Visual web development tools

SublimeText3 Mac version
God-level code editing software (SublimeText3)

Hot Topics

Regarding the problem of removing the Python interpreter that comes with Linux systems, many Linux distributions will preinstall the Python interpreter when installed, and it does not use the package manager...

Pylance type detection problem solution when using custom decorator In Python programming, decorator is a powerful tool that can be used to add rows...

About Pythonasyncio...

Using python in Linux terminal...

Loading pickle file in Python 3.6 environment error: ModuleNotFoundError:Nomodulenamed...

Compatibility issues between Python asynchronous libraries In Python, asynchronous programming has become the process of high concurrency and I/O...

Error loading Pickle file in Python 3.6 environment: ModuleNotFoundError:Nomodulenamed...

The problem and solution of the child process continuing to run when using signals to kill the parent process. In Python programming, after killing the parent process through signals, the child process still...
