首頁 後端開發 php教程 PHP資料結構:堆資料結構的奧妙,實現高效率的排序與優先權佇列

PHP資料結構:堆資料結構的奧妙,實現高效率的排序與優先權佇列

Jun 01, 2024 pm 03:54 PM
堆疊 php資料結構

PHP 中的堆資料結構是一種滿足完全二元樹和堆性質(父結點值大於/小於子結點值)的樹狀結構,使用陣列實現。堆支援兩種操作:排序(從小到大提取最大元素)和優先權隊列(根據優先權提取最大元素),分別透過 heapifyUp 和 heapifyDown 方法維護堆的性質。

PHP資料結構:堆資料結構的奧妙,實現高效率的排序與優先權佇列

PHP 中的堆疊資料結構:揭秘排序與優先權佇列的奧秘

堆疊是一種樹狀資料結構,它滿足以下兩個性質:

  • 完全二元樹性質:樹中的每個結點都有兩個子結點,或沒有子結點,形成一棵完全二元樹。
  • 堆性質:每個父結點的值都大於(或等於)它的兩個子結點的值(最大堆)或小於(或等於)它的兩個子結點的值(最小堆)。

PHP 實作

在 PHP 中,我們使用陣列來實作堆疊。以下是一個最大堆的PHP 實作:

class MaxHeap {
    private $heap = array();
    private $size = 0;

    public function insert($value) {
        $this->heap[$this->size++] = $value;
        $this->heapifyUp($this->size - 1);
    }

    private function heapifyUp($index) {
        if ($index === 0) {
            return;
        }
        $parentIndex = intval(($index - 1) / 2);
        if ($this->heap[$index] > $this->heap[$parentIndex]) {
            $temp = $this->heap[$index];
            $this->heap[$index] = $this->heap[$parentIndex];
            $this->heap[$parentIndex] = $temp;
            $this->heapifyUp($parentIndex);
        }
    }

    public function extractMax() {
        if ($this->size === 0) {
            return null;
        }
        $max = $this->heap[0];
        $this->heap[0] = $this->heap[$this->size - 1];
        $this->size--;
        $this->heapifyDown(0);
        return $max;
    }

    private function heapifyDown($index) {
        $largestIndex = $index;
        $leftIndex = 2 * $index + 1;
        $rightIndex = 2 * $index + 2;
        if ($leftIndex < $this->size && $this->heap[$leftIndex] > $this->heap[$largestIndex]) {
            $largestIndex = $leftIndex;
        }
        if ($rightIndex < $this->size && $this->heap[$rightIndex] > $this->heap[$largestIndex]) {
            $largestIndex = $rightIndex;
        }
        if ($largestIndex !== $index) {
            $temp = $this->heap[$index];
            $this->heap[$index] = $this->heap[$largestIndex];
            $this->heap[$largestIndex] = $temp;
            $this->heapifyDown($largestIndex);
        }
    }
}
登入後複製

實戰案例

排序:

$heap = new MaxHeap();
$heap->insert(10);
$heap->insert(5);
$heap->insert(15);
$heap->insert(8);
$heap->insert(12);

while ($heap->size > 0) {
    echo $heap->extractMax() . " ";
}
登入後複製

輸出:15 12 10 8 5

優先權佇列:

$heap = new MaxHeap();
$heap->insert(5);
$heap->insert(2);
$heap->insert(3);
$heap->insert(1);

while ($heap->size > 0) {
    $element = $heap->extractMax();
    echo "服务于元素 " . $element . "\n";
}
登入後複製

輸出:
服務於元素5
服務於元素3
服務於元素2
服務於元素1

以上是PHP資料結構:堆資料結構的奧妙,實現高效率的排序與優先權佇列的詳細內容。更多資訊請關注PHP中文網其他相關文章!

本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn

熱AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智慧驅動的應用程序,用於創建逼真的裸體照片

AI Clothes Remover

AI Clothes Remover

用於從照片中去除衣服的線上人工智慧工具。

Undress AI Tool

Undress AI Tool

免費脫衣圖片

Clothoff.io

Clothoff.io

AI脫衣器

Video Face Swap

Video Face Swap

使用我們完全免費的人工智慧換臉工具,輕鬆在任何影片中換臉!

熱工具

記事本++7.3.1

記事本++7.3.1

好用且免費的程式碼編輯器

SublimeText3漢化版

SublimeText3漢化版

中文版,非常好用

禪工作室 13.0.1

禪工作室 13.0.1

強大的PHP整合開發環境

Dreamweaver CS6

Dreamweaver CS6

視覺化網頁開發工具

SublimeText3 Mac版

SublimeText3 Mac版

神級程式碼編輯軟體(SublimeText3)

Python中的Deque: 實作高效的佇列與堆疊 Python中的Deque: 實作高效的佇列與堆疊 Apr 12, 2023 pm 09:46 PM

Python 中的 deque 是一個低階的、高度最佳化的雙端佇列,對於實現優雅、高效的Pythonic 佇列和堆疊很有用,它們是計算中最常見的列表式資料類型。本文中,雲朵君將和大家一起學習如下:開始使用deque有效地彈出和追加元素訪問deque中的任意元素用deque構建高效隊列開始使用Deque向Python 列表的右端追加元素和彈出元素的操作,一般非常高效。如果用大 O 表示時間複雜性,那麼可以說它們是 O(1)。而當 Python 需要重新分配記憶體來增加底層列表以接受新的元素時,這些

heap和stack有什麼差別 heap和stack有什麼差別 Nov 22, 2022 pm 04:12 PM

區別:1、堆(heap)的空間一般由程式設計師分配釋放;而堆疊(stack)的空間由作業系統自動分配釋放 。 2、heap是存放在二級快取中,生命週期由虛擬機器的垃圾回收演算法決定;而stack使用的是一級緩存,通常都是被呼叫時處於儲存空間中,調用完畢立即釋放。 3.資料結構不同,heap可以被看成是一棵樹,而stack是一種先進後出的資料結構。

堆積和棧的區別 堆積和棧的區別 Jul 18, 2023 am 10:17 AM

堆和棧的區別:1、記憶體分配方式不同,堆是由程式設計師手動分配和釋放的,而棧是由作業系統自動分配和釋放的;2、大小不同,棧的大小是固定的,而堆的大小是動態成長的;3、資料存取方式不同,在堆中,資料的存取是透過指標來實現的,而在堆疊中,資料的存取是透過變數名稱來實現的;4、資料的生命週期,在堆中,資料的生命週期可以很長,而在堆疊中,變數的生命週期是由其所在的作用域來決定的。

java堆和堆疊有哪些差別 java堆和堆疊有哪些差別 Dec 25, 2023 pm 05:29 PM

java堆和堆疊的區別:1、記憶體分配和管理;2、儲存內容;3、執行緒執行和生命週期;4、效能影響。詳細介紹:1、記憶體分配和管理,Java堆是動態分配的記憶體區域,主要用來儲存物件實例,在Java中,物件是透過堆疊記憶體進行分配的,當建立一個物件時,Java虛擬機會在堆上分配相應的記憶體空間,並自動進行垃圾回收和記憶體管理,堆的大小可以在運行時動態調整,透過JVM參數進行配置等等。

PHP資料結構:堆資料結構的奧妙,實現高效率的排序與優先權佇列 PHP資料結構:堆資料結構的奧妙,實現高效率的排序與優先權佇列 Jun 01, 2024 pm 03:54 PM

PHP中的堆資料結構是一種滿足完全二元樹和堆性質(父結點值大於/小於子結點值)的樹狀結構,使用陣列實作。堆支援兩種操作:排序(從小到大提取最大元素)和優先權隊列(根據優先權提取最大元素),分別透過heapifyUp和heapifyDown方法維護堆的性質。

Go語言中的堆疊、堆疊、字典、紅黑樹等資料結構 Go語言中的堆疊、堆疊、字典、紅黑樹等資料結構 Jun 03, 2023 pm 03:10 PM

隨著電腦科學的發展,資料結構成為了一門重要的學科。在軟體開發中,資料結構是非常重要的,它們可以提高程式效率和可讀性,同時也可以幫助解決各種問題。在Go語言中,堆疊、堆疊、字典、紅黑樹等資料結構也是非常重要的。本文將介紹這些資料結構及其在Go語言中的實作。堆堆(Heap)是一個經典的資料結構,用來解決優先隊列問題。優先隊列指的是一種隊列,在取出元素的時候,按照元

C++中的堆和優先隊列 C++中的堆和優先隊列 Aug 22, 2023 pm 04:16 PM

堆和優先佇列是C++中常用的資料結構,它們都具有重要的應用價值。本文將分別對堆和優先隊列進行介紹和解析,以幫助讀者更好地理解和使用它們。一、堆堆是一種特殊的樹狀資料結構,它可以用來實作優先權佇列。在堆中,每個節點都滿足如下性質:它的值不小於(或不大於)其父節點的值。它的左右子樹也是一堆。我們將不小於其父節點的堆稱為“最小堆”,將不大於其父節點的堆稱為“最大堆”

Python中的堆和優先隊列的使用場景有哪些? Python中的堆和優先隊列的使用場景有哪些? Oct 28, 2023 am 08:56 AM

Python中的堆和優先隊列的使用場景有哪些?堆是一種特殊的二元樹結構,常用於有效率地維護一個動態的集合。 Python中的heapq模組提供了堆的實現,可以方便地進行堆的操作。優先隊列也是一種特殊的資料結構,不同於普通的佇列,它的每個元素都有一個與之相關的優先權。最高優先順序的元素先被取出。 Python中的heapq模組也可以實現優先權佇列的功能。下面我們介紹一些

See all articles