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

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

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

1. 概述

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

2. 堆的基本操作

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

A:用于表示堆的數(shù)組,下標(biāo)從1開始,一直到n
PARENT(t):節(jié)點(diǎn)t的父節(jié)點(diǎn),即floor(t/2)
RIGHT(t):節(jié)點(diǎn)t的左孩子節(jié)點(diǎn),即:2*t
LEFT(t):節(jié)點(diǎn)t的右孩子節(jié)點(diǎn),即:2*t+1
HEAP_SIZE(A):堆A當(dāng)前的元素?cái)?shù)目
下面給出其主要的四個(gè)操作(以大頂堆為例):
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)化成一個(gè)大頂堆。思想是,先找到堆的最后一個(gè)非葉子節(jié)點(diǎn)(即為第n/2個(gè)節(jié)點(diǎn)),然后從該節(jié)點(diǎn)開始,從后往前逐個(gè)調(diào)整每個(gè)子樹,使之稱為堆,最終整個(gè)數(shù)組便是一個(gè)堆。
復(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)
該操作主要是獲取堆中最大的元素,同時(shí)保持堆的基本性質(zhì)。堆的最大元素即為第一個(gè)元素,將其保存下來,同時(shí)將最后一個(gè)元素放到A[1]位置,之后從上往下調(diào)整A,使之成為一個(gè)堆。
復(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)
向堆中添加一個(gè)元素t,同時(shí)保持堆的性質(zhì)。算法思想是,將t放到A的最后,然后從該元素開始,自下向上調(diào)整,直至A成為一個(gè)大頂堆。
復(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)用是堆排序,時(shí)間復(fù)雜度為O(N lg N)。如果是從小到大排序,用大頂堆;從大到小排序,用小頂堆。

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

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

4. 總結(jié)

堆是一種非常基礎(chǔ)但很實(shí)用的數(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ù)乘積的溢出問題是指兩個(gè)整數(shù)相乘得到的結(jié)果超過了所能表示的數(shù)據(jù)類型的范圍,本文給大家介紹了C/C++整數(shù)乘積的溢出問題的解決,需要的朋友可以參考下
    2024-02-02
  • C++實(shí)現(xiàn)Huffman的編解碼

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

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

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

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

    C++ const的各種用法詳解

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

    c語(yǔ)言switch反匯編的實(shí)現(xiàn)

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

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

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

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

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

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

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

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

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

    讓我們一起來對(duì)C語(yǔ)言指針再分析

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

最新評(píng)論