国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

PHP面試:說下什么是堆和堆排序?

twohappy / 1962人閱讀

摘要:一個常見的例子就是優先隊列,還有排序算法之一的堆排序。另外我們還將學習堆排序,并將使用實現堆。堆排序在堆排序中,我們需要用給定的值構建一個一個堆。偽代碼如下從上面的偽代碼可以看到,堆排序的第一步就是構建一個堆。

堆是什么?

堆是基于樹抽象數據類型的一種特殊的數據結構,用于許多算法和數據結構中。一個常見的例子就是優先隊列,還有排序算法之一的堆排序。這篇文章我們將討論堆的屬性、不同類型的堆以及
堆的常見操作。另外我們還將學習堆排序,并將使用SPL實現堆。

根據定義,堆是一個擁有堆特性的樹形數據結構。如果父節點大于子節點,那么它被稱為最大堆,如果父節點小于子節點,則稱為最小堆。下圖是最大堆的例子

我們看根節點,值100大于兩個子節點19和36。對于19來說,該值大于17和3。其他節點也適用相同的規則。我們可以看到,這棵樹沒有完全排序。但重要的事實是我們總能找到樹的最大值或最小值,在許多特殊的情況下這是非常有用的。

堆結構有很多種,如二叉堆、B堆、斐波那契堆、三元堆,樹堆、弱堆等。二叉堆是堆實現中最流行的一種。二叉堆是一個完全二叉樹(不了解二叉樹的朋友可以看PHP實現二叉樹),樹的所有內部節點都被完全填充,最后一層可以完全填充的或部分填充。對于二叉堆,我們可以在對數時間復雜度內執行大部分操作。

堆的操作

堆是一個特殊的樹數據結構。我們首先根據給定的數據構建堆。由于堆有嚴格的構建規則,所以我們每一步操作都必須滿足這個規則。下面是堆的一些核心操作。

創建堆

插入新值

從堆中提取最小值或最大值

刪除一個值

交換

從給定的項或數字集合創建堆需要我們確保堆規則和二叉樹屬性得到滿足。這意味著父節點必須大于或小于子節點。對于樹中的所有節點,都需要遵守這個規則。同樣,樹必須是一個完全的二叉樹。在創建堆時,我們從一個節點開始,并向堆中插入一個新節點。

當插入節點操作時,我們不能從任意節點開始。插入操作如下

將新節點插入堆的底部

檢查新節點和父節點的大小順序,如果它們是正確的順序,停止。

如果它們不是正確的順序,交換它們然后繼續前一步的檢查。這一步驟與前一步一起被稱為篩分或上升,等等。

提取操作(最小或最大)即從堆中取出根節點。在此之后,我們必須執行下列操作以確保剩余節點然仍符合堆的特點。

從堆移動最后一個節點作為新根

將新根節點與子節點進行比較,如果它們處于正確的順序,則停止。

如果不是,則將根節點與子節點交換(當是小根堆時為最小子節點,當大根堆時為最大子節點)并繼續前面的步驟。這一步與前一個步驟一起被稱為下堆。

在堆中,一個重要的操作是交換。現在我們將使用PHP7來實現二叉堆。

namespace DataStructureHeap;

class MaxHeap
{
    public $heap;
    public $count;

    public function __construct(int $size)
    {
        //初始化堆
        $this->heap = array_fill(0, $size, 0);
        $this->count = 0;
    }

    public function create(array $arr = [])
    {
        array_map(function($item){
            $this->insert($item);
        }, $arr);
    }

    public function insert(int $data)
    {
        //插入數據操作
        if ($this->count == 0) {
            //插入第一條數據
            $this->heap[0] = $data;
            $this->count = 1;
        } else {
            //新插入的數據放到堆的最后面
            $this->heap[$this->count++] = $data;
            //上浮到合適位置
            $this->siftUp();
        }
    }

    public function display()
    {
        return implode(" ", array_slice($this->heap, 0));
    }

    public function siftUp()
    {
        //待上浮元素的臨時位置
        $tempPos = $this->count - 1;    
        //根據完全二叉樹性質找到副節點的位置
        $parentPos = intval($tempPos / 2);

        while ($tempPos > 0 && $this->heap[$parentPos] < $this->heap[$tempPos]) {
            //當不是根節點并且副節點的值小于臨時節點的值,就交換兩個節點的值
            $this->swap($parentPos, $tempPos);
            //重置上浮元素的位置
            $tempPos = $parentPos;
            //重置父節點的位置
            $parentPos = intval($tempPos / 2);
        }
    }

    public function swap(int $a, int $b)
    {
        $temp = $this->heap[$a];
        $this->heap[$a] = $this->heap[$b];
        $this->heap[$b] = $temp;
    }

    public function extractMax()
    {
        //最大值就是大跟堆的第一個值
        $max = $this->heap[0];
        //把堆的最后一個元素作為臨時的根節點
        $this->heap[0] = $this->heap[$this->count - 1];
        //把最后一個節點重置為0
        $this->heap[--$this->count] = 0;
        //下沉根節點到合適的位置
        $this->siftDown(0);

        return $max;
    }

    public function siftDown(int $k)
    {
        //最大值的位置
        $largest = $k;
        //左孩子的位置
        $left = 2 * $k + 1;
        //右孩子的位置
        $right = 2 * $k + 2;


        if ($left < $this->count && $this->heap[$largest] < $this->heap[$left]) {
            //如果左孩子大于最大值,重置最大值的位置為左孩子
            $largest = $left;
        }

        if ($right < $this->count && $this->heap[$largest] < $this->heap[$right]) {
            //如果右孩子大于最大值,重置最大值的位置為左孩子
            $largest = $right;
        }


        //如果最大值的位置發生改變
        if ($largest != $k) {
            //交換位置
            $this->swap($largest, $k);
            //繼續下沉直到初始位置不發生改變
            $this->siftDown($largest);
        }
    }
}
復雜度分析

因為不同種類的堆有不同的實現,所以各種堆實現也有不同的復雜度。但是有一個堆的操作在各類實現中都是O(1)的復雜度,就是獲取最大值或者最小值。我看來看下二分堆的復雜度分析。

操作 平均復雜度 最壞復雜度
Search O(n) O(n)
Insert O(1) O(log n)
Delete O(log n) O(log n)
Extract O(1) O(1)

因為二叉堆不是完全排序的,所以搜索操作會比二叉搜索樹花更多的時間。

堆與優先隊列

一個最常用的操作就是將堆當作優先隊列來使用。在PHP實現棧和PHP實現隊列中,我們已經了解到優先隊列是一種根據元素權重而不是入隊順序來進行出隊操作的結構。我們已經用鏈表實現優先隊列和Spl實現優先隊列,現在我們使用堆來實現優先隊列。

namespace DataStructureHeap;

class PriorityQueue extends MaxHeap
{
    public function __construct(int $size)
    {
        parent::__construct($size);
    }

    public function enqueue(int $val)
    {
        parent::insert($val);
    }

    public function dequeue()
    {
        return parent::extractMax();
    }
}
堆排序

在堆排序中,我們需要用給定的值構建一個一個堆。然后連續的檢查堆的值以確保任何時候整個堆都是排序的。在正常的堆結構中,我們每當插入一個新的值到合適位置之后就停止檢查,但是在堆排序中,只要有下一個值,我們就不斷的去檢查構建堆。偽代碼如下:

HeapSort(A)
BuildHeap(A)
for i = n-1 to 0
swap(A[0],A[i])
n = n - 1
Heapify(A, 0)

BuildHeap(A)
n = elemens_in(A)
for i = floor(n / 2) to 0
Heapify(A, i)

Heapify(A, i)
left = 2i+1;
right = 2i + 2;
max = i

if (left < n and A[left] > A[i])
max = left
if (right < n and A[right] > A[max])
max = right

if (max != i)
swap(A[i], A[max])
Heapify(A, max)

從上面的偽代碼可以看到,堆排序的第一步就是構建一個堆。每次我們向堆中添加新的元素,我們都調用heapify來滿足堆的特性。一旦堆構建好之后,我們對所有的元素都進行檢查,下面使用PHP的實現堆排序。完整的代碼可以點這里查看。

function heapSort(&$arr)
{
    $length = count($arr);
    buildHeap($arr);
    $heapSize = $length - 1;
    for ($i = $heapSize; $i >= 0; $i--) {
        list($arr[0], $arr[$heapSize]) = [$arr[$heapSize], $arr[0]];
        $heapSize--;
        heapify(0, $heapSize, $arr);
    }
}

function buildHeap(&$arr)
{
    $length = count($arr);
    $heapSize = $length - 1;
    for ($i = ($length / 2); $i >= 0; $i--) {
        heapify($i, $heapSize, $arr);
    }
}

function heapify(int $k, int $heapSize, array &$arr)
{
    $largest = $k;
    $left = 2 * $k + 1;
    $right = 2 * $k + 2;

    if ($left <= $heapSize && $arr[$k] < $arr[$left]) {
        $largest = $left;
    }

    if ($right <= $heapSize && $arr[$largest] < $arr[$right]) {
        $largest = $right;
    }

    if ($largest != $k) {
        list($arr[$largest], $arr[$k]) = [$arr[$k], $arr[$largest]];
        heapify($largest, $heapSize, $arr);
    }
}

堆排序的時間復雜度為O(nlog n),空間復雜度為O(1)。對比歸并排序,堆排序有更好的表現。

PHP中的SplHeap、SplMinHeap和SplMaxHeap

當然,方便的PHP內置的標準庫已經幫助我實現了堆,你可以通過SplHeapSplMinHeapSplMaxHeap來使用它們。

更多內容

PHP基礎數據結構專題系列目錄: 地址。主要使用PHP語法總結基礎的數據結構和算法。還有我們日常PHP開發中容易忽略的基礎知識和現代PHP開發中關于規范、部署、優化的一些實戰性建議,同時還有對Javascript語言特點的深入研究。

文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。

轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/29278.html

相關文章

  • 堆和

    摘要:百度百科上對堆和棧進行了對比分析堆棧空間分配棧操作系統由操作系統自動分配釋放,存放函數的參數值,局部變量的值等。堆棧緩存方式棧使用的是一級緩存,他們通常都是被調用時處于存儲空間中,調用完畢立即釋放。顯然,堆的效率比棧要低得多。 相信很多程序員對于堆和棧的概念,總是感覺很朦朧,感覺在哪里聽過見過,并沒有深交。 在計算機領域,堆棧是一個不容忽視的概念,我們編寫的C語言程序基本上都要用到。但...

    lscho 評論0 收藏0
  • 數據結構與算法——堆

    摘要:堆排序的時間復雜度非常的穩定,是,并且是原地排序算法,具體是怎么實現的呢我們一般把堆排序分為兩個步驟建堆和排序。 1. 什么是堆 堆(Heap),其實是一種特殊的二叉樹,主要滿足了二叉樹的兩個條件: 堆是一種完全二叉樹,還記得完全二叉樹的定義嗎?葉節點都在最底下兩層,最后一層的節點都靠左排列,并且除了最后一層,其他層的節點個數都要達到最大,這種樹叫做完全二叉樹。 堆中的每個節點的值都...

    hankkin 評論0 收藏0
  • JVM的基本概念與維護調優

    摘要:棧因為是運行單位,因此里面存儲的信息都是跟當前線程相關的信息。基本類型和對象的引用都是在存放在棧中,而且都是幾個字節的一個數,因此在程序運行時,他們的處理方式是統一的。對象,是由基本類型組成的。 一、概念 數據類型 java虛擬機中,數據類型可以分為兩類: 基本類型 引用類型 基本類型的變量保存原始值,即:他代表的值就是數值本身;而引用類型的變量保存引用值。基本類型包括:byte,sh...

    DevWiki 評論0 收藏0

發表評論

0條評論

twohappy

|高級講師

TA的文章

閱讀更多
最新活動
閱讀需要支付1元查看
<