欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

數(shù)據(jù)結(jié)構(gòu)之堆詳解

 更新時間:2014年08月28日 09:18:16   投稿:junjie  
這篇文章主要介紹了數(shù)據(jù)結(jié)構(gòu)之堆詳解,本文講解了堆的基本常識堆的基本操作、堆的應(yīng)用等內(nèi)容,需要的朋友可以參考下

1. 概述

堆(也叫優(yōu)先隊列),是一棵完全二叉樹,它的特點是父節(jié)點的值大于(小于)兩個子節(jié)點的值(分別稱為大頂堆和小頂堆)。它常用于管理算法執(zhí)行過程中的信息,應(yīng)用場景包括堆排序,優(yōu)先隊列等。

2. 堆的基本操作

堆是一棵完全二叉樹,高度為O(lg n),其基本操作至多與樹的高度成正比。在介紹堆的基本操作之前,先介紹幾個基本術(shù)語:

A:用于表示堆的數(shù)組,下標從1開始,一直到n
PARENT(t):節(jié)點t的父節(jié)點,即floor(t/2)
RIGHT(t):節(jié)點t的左孩子節(jié)點,即:2*t
LEFT(t):節(jié)點t的右孩子節(jié)點,即:2*t+1
HEAP_SIZE(A):堆A當前的元素數(shù)目
下面給出其主要的四個操作(以大頂堆為例):
2.1 Heapify(A,n,t)
該操作主要用于維持堆的基本性質(zhì)。假定以RIGHT(t)和LEFT(t)為根的子樹都已經(jīng)是堆,然后調(diào)整以t為根的子樹,使之成為堆。

復(fù)制代碼 代碼如下:

void Heapify(int A[], int n, int t)
 
{
 
  int left = LEFT(t);
 
  int right = RIGHT(t);
 
  int max = t;
 
  if(left <= n)     max = A[left] > A[max] ? left : max;
 
  if(right <= n)     max = A[right] > A[max] ? right : max;
 
  if(max != A[t])
 
  {
 
    swap(A, max, t);
 
    Heapify(A, n, max);
 
  }
 
}

2.2  BuildHeap(A,n)
該操作主要是將數(shù)組A轉(zhuǎn)化成一個大頂堆。思想是,先找到堆的最后一個非葉子節(jié)點(即為第n/2個節(jié)點),然后從該節(jié)點開始,從后往前逐個調(diào)整每個子樹,使之稱為堆,最終整個數(shù)組便是一個堆。
復(fù)制代碼 代碼如下:

void BuildHeap(int A[], int n)
 
{
 
  int i;
 
  for(i = n/2; i<=n; i++)
 
  Heapify(A, n, i);
 
}

2.3 GetMaximum(A,n)
該操作主要是獲取堆中最大的元素,同時保持堆的基本性質(zhì)。堆的最大元素即為第一個元素,將其保存下來,同時將最后一個元素放到A[1]位置,之后從上往下調(diào)整A,使之成為一個堆。
復(fù)制代碼 代碼如下:

void GetMaximum(int A[], int n)
 
{
 
  int max = A[1];
 
  A[1] = A[n];
 
  n--;
 
  Heapify(A, n, 1);
 
  return max;
 
}

2.4  Insert(A, n, t)
向堆中添加一個元素t,同時保持堆的性質(zhì)。算法思想是,將t放到A的最后,然后從該元素開始,自下向上調(diào)整,直至A成為一個大頂堆。
復(fù)制代碼 代碼如下:

void Insert(int A[], int n, int t)
 
{
 
  n++;
 
  A[n] = t;
 
  int p = n;
 
  while(p >1 && A[PARENT(p)] < t)
 
  {
 
    A[p] = A[PARENT(p)];
 
    p = PARENT(p);
 
  }
 
  A[p] = t;
 
  return max;
 
}

3.  堆的應(yīng)用

3.1  堆排序
堆的最常見應(yīng)用是堆排序,時間復(fù)雜度為O(N lg N)。如果是從小到大排序,用大頂堆;從大到小排序,用小頂堆。

3.2  在O(n lg k)時間內(nèi),將k個排序表合并成一個排序表,n為所有有序表中元素個數(shù)。

【解析】取前100 萬個整數(shù),構(gòu)造成了一棵數(shù)組方式存儲的具有小頂堆,然后接著依次取下一個整數(shù),如果它大于最小元素亦即堆頂元素,則將其賦予堆頂元素,然后用Heapify調(diào)整整個堆,如此下去,則最后留在堆中的100萬個整數(shù)即為所求 100萬個數(shù)字。該方法可大大節(jié)約內(nèi)存。
3.3 一個文件中包含了1億個隨機整數(shù),如何快速的找到最大(小)的100萬個數(shù)字?(時間復(fù)雜度:O(n lg k))

4. 總結(jié)

堆是一種非?;A(chǔ)但很實用的數(shù)據(jù)結(jié)構(gòu),很多復(fù)雜算法或者數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)就是堆,因而,了解和掌握堆這種數(shù)據(jù)結(jié)構(gòu)顯得尤為重要。

5. 參考資料

(1)經(jīng)典算法教程《算法導(dǎo)論》

相關(guān)文章

  • C/C++整數(shù)乘積的溢出問題的解決

    C/C++整數(shù)乘積的溢出問題的解決

    整數(shù)乘積的溢出問題是指兩個整數(shù)相乘得到的結(jié)果超過了所能表示的數(shù)據(jù)類型的范圍,本文給大家介紹了C/C++整數(shù)乘積的溢出問題的解決,需要的朋友可以參考下
    2024-02-02
  • C++實現(xiàn)Huffman的編解碼

    C++實現(xiàn)Huffman的編解碼

    這篇文章主要為大家詳細介紹了C++實現(xiàn)Huffman的編解碼,文中示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2020-04-04
  • 從C語言過渡到C++之引用(別名)

    從C語言過渡到C++之引用(別名)

    本文給大家講解的是在從C語言過渡到C++中的引用的區(qū)別及簡單示例,有需要的小伙伴可以參考下
    2017-07-07
  • C++ const的各種用法詳解

    C++ const的各種用法詳解

    const名叫常量限定符,用來限定特定變量,以通知編譯器該變量是不可修改的。習慣性的使用const,可以避免在函數(shù)中對某些不應(yīng)修改的變量造成可能的改動。本文主要談?wù)刢onst的用法,感興趣的同學(xué)可以參考閱讀
    2023-04-04
  • c語言switch反匯編的實現(xiàn)

    c語言switch反匯編的實現(xiàn)

    本文主要介紹了c語言switch反匯編,在分支較多的時候,switch的效率比if高,在反匯編中我們即可看到效率高的原因,感興趣的可以了解一下
    2021-06-06
  • c++中關(guān)于max_element()函數(shù)解讀

    c++中關(guān)于max_element()函數(shù)解讀

    這篇文章主要介紹了c++中關(guān)于max_element()函數(shù)解讀,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教
    2023-02-02
  • C語言fgetc和fputc函數(shù)用法詳解(以字符形式讀寫文件)

    C語言fgetc和fputc函數(shù)用法詳解(以字符形式讀寫文件)

    這篇文章主要介紹了C語言fgetc和fputc函數(shù)用法詳解(以字符形式讀寫文件),文中通過示例代碼介紹的非常詳細,對大家的學(xué)習或者工作具有一定的參考學(xué)習價值,需要的朋友們下面隨著小編來一起學(xué)習學(xué)習吧
    2021-01-01
  • C++常量指針,指針常量,指向常量的常指針詳解

    C++常量指針,指針常量,指向常量的常指針詳解

    剛接觸到指針時,關(guān)于C++常量指針,指針常量,指向常量的常指針容易混淆,所以整理下,希望能夠幫助自己也幫助到大家
    2021-10-10
  • C++使用鏈表存儲實現(xiàn)通訊錄功能管理

    C++使用鏈表存儲實現(xiàn)通訊錄功能管理

    這篇文章主要為大家詳細介紹了C++使用鏈表存儲實現(xiàn)通訊錄功能管理,文中示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2022-06-06
  • 讓我們一起來對C語言指針再分析

    讓我們一起來對C語言指針再分析

    這篇文章主要為大家詳細介紹C語言的指針,本文進行了深度解析,文中示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下,希望能夠給你帶來幫助
    2022-01-01

最新評論