当前位置:天才代写 > tutorial > 大数据教程 > 数据结构之堆

数据结构之堆

2021-02-14 17:57 星期日 所属: 大数据教程 浏览:76

1. 简述

堆(也叫优先队列),是一棵完全二叉树,它的特性是父节点的值超过(低于)两个子连接点的值(各自称之为大顶堆和小顶堆)。它常见于管理方法优化算法实行全过程中的信息内容,应用领域包含堆排序,优先队列等。

2. 堆的操作过程

堆是一棵完全二叉树,高宽比为O(lg n),其操作过程最多与树的高宽比正相关。在详细介绍堆的操作过程以前,先详细介绍好多个基础专业术语:

  • A:用以表明堆的二维数组,字符从1逐渐,一直到n
  • PARENT(t):连接点t的父节点,即floor(t/2)
  • RIGHT(t):连接点t的左小孩连接点,即:2*t
  • LEFT(t):连接点t的右小孩连接点,即:2*t 1
  • HEAP_SIZE(A):堆A当今的原素数量

下边得出其关键的四个实际操作(以大顶堆为例子):

2.1 Heapify(A,n,t)

该实际操作关键用以保持堆的基础特性。假设以RIGHT(t)和LEFT(t)为根的子树都早已是堆,随后调节以t为根的子树,使之变成堆。

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)

该实际操作主要是将二维数组A转换成一个大顶堆。观念是,先寻找堆的最后一个非叶子节点(即是第n/两个连接点),随后从该连接点逐渐,从后面向前逐一调节每一个子树,使之称之为堆,最后全部二维数组就是一个堆。

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

2.3 GetMaximum(A,n)

该实际操作主要是获得堆中较大 的原素,另外维持堆的基础特性。堆的较大 原素即是第一个原素,将其储存出来,另外将最后一个原素放进A[1]部位,以后从上向下调节A,使之变成一个堆。

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,另外维持堆的特性。优化算法观念是,将t放进A的最终,随后从该原素逐渐,自下往上调节,直到A变成一个大顶堆。

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.  堆的运用

3.1  堆排序

堆的最普遍运用是堆排序,算法复杂度为O(N lg N)。如果是由小到大排列,用大顶堆;从大到小排列,用小顶堆。

3.2  在O(n lg k)時间内,将k个排列表合拼成一个排列表,n为全部有序表中原素数量。

【分析】取前100 万只整数金额,结构变成一棵二维数组方法储存的具备小顶堆,随后然后先后取下一个整数金额,假如它超过最少原素亦即堆顶原素,则将其授予堆顶原素,随后用Heapify调节全部堆,这般下来,则最终留到堆中的一百万个整数金额即是所愿 一百万个数据。该方式可大大的节省运行内存。

3.3 一个文档中包括了一亿个任意整数金额,怎么才能的寻找较大 (小)的一百万个数据?(算法复杂度:O(n lg k))

4. 小结

堆是一种十分基本但很好用的算法设计,许多 繁杂优化算法或是算法设计的基本便是堆,因此,掌握和把握堆这类算法设计看起来至关重要。

5. 参考文献

(1)经典算法实例教程《算法导论》

 

    关键字:

天才代写-代写联系方式