Rumah pembangunan bahagian belakang Tutorial Python python计算最大优先级队列实例

python计算最大优先级队列实例

Jun 06, 2016 am 11:28 AM
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))])

Kenyataan Laman Web ini
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn

Tag artikel panas

Notepad++7.3.1

Notepad++7.3.1

Editor kod yang mudah digunakan dan percuma

SublimeText3 versi Cina

SublimeText3 versi Cina

Versi Cina, sangat mudah digunakan

Hantar Studio 13.0.1

Hantar Studio 13.0.1

Persekitaran pembangunan bersepadu PHP yang berkuasa

Dreamweaver CS6

Dreamweaver CS6

Alat pembangunan web visual

SublimeText3 versi Mac

SublimeText3 versi Mac

Perisian penyuntingan kod peringkat Tuhan (SublimeText3)

Cara Muat turun DeepSeek Xiaomi Cara Muat turun DeepSeek Xiaomi Feb 19, 2025 pm 05:27 PM

Cara Muat turun DeepSeek Xiaomi

Apakah kelebihan dan kekurangan templat? Apakah kelebihan dan kekurangan templat? May 08, 2024 pm 03:51 PM

Apakah kelebihan dan kekurangan templat?

Google AI mengumumkan Gemini 1.5 Pro dan Gemma 2 untuk pembangun Google AI mengumumkan Gemini 1.5 Pro dan Gemma 2 untuk pembangun Jul 01, 2024 am 07:22 AM

Google AI mengumumkan Gemini 1.5 Pro dan Gemma 2 untuk pembangun

Dengan hanya $250, pengarah teknikal Hugging Face mengajar anda cara memperhalusi Llama 3 Dengan hanya $250, pengarah teknikal Hugging Face mengajar anda cara memperhalusi Llama 3 May 06, 2024 pm 03:52 PM

Dengan hanya $250, pengarah teknikal Hugging Face mengajar anda cara memperhalusi Llama 3

Kongsi beberapa rangka kerja projek berkaitan AI dan LLM sumber terbuka .NET Kongsi beberapa rangka kerja projek berkaitan AI dan LLM sumber terbuka .NET May 06, 2024 pm 04:43 PM

Kongsi beberapa rangka kerja projek berkaitan AI dan LLM sumber terbuka .NET

Panduan lengkap untuk penyahpepijatan dan analisis fungsi golang Panduan lengkap untuk penyahpepijatan dan analisis fungsi golang May 06, 2024 pm 02:00 PM

Panduan lengkap untuk penyahpepijatan dan analisis fungsi golang

Bagaimana anda bertanya kepadanya Deepseek Bagaimana anda bertanya kepadanya Deepseek Feb 19, 2025 pm 04:42 PM

Bagaimana anda bertanya kepadanya Deepseek

Bagaimana untuk menyimpan fungsi menilai Bagaimana untuk menyimpan fungsi menilai May 07, 2024 am 01:09 AM

Bagaimana untuk menyimpan fungsi menilai

See all articles