快捷導(dǎo)航

數(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)論》

您可能感興趣的文章: