当前位置:  编程技术>c/c++/嵌入式

数据结构之堆详解

    来源: 互联网  发布时间:2014-10-27

    本文导语:  1. 概述 堆(也叫优先队列),是一棵完全二叉树,它的特点是父节点的值大于(小于)两个子节点的值(分别称为大顶堆和小顶堆)。它常用于管理算法执行过程中的信息,应用场景包括堆排序,优先队列等。 2. 堆的基本操...

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 A[max] ? left : max;
 
  if(right A[max] ? right : max;
 
  if(max != A[t])
 
  {
 
    swap(A, max, t);
 
    Heapify(A, n, max);
 
  }
 
}

2.2  BuildHeap(A,n)
该操作主要是将数组A转化成一个大顶堆。思想是,先找到堆的最后一个非叶子节点(即为第n/2个节点),然后从该节点开始,从后往前逐个调整每个子树,使之称为堆,最终整个数组便是一个堆。
代码如下:

void BuildHeap(int A[], int n)
 
{
 
  int i;
 
  for(i = n/2; i1 && 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调整整个堆,如此下去,则最后留在堆中的100万个整数即为所求 100万个数字。该方法可大大节约内存。
3.3 一个文件中包含了1亿个随机整数,如何快速的找到最大(小)的100万个数字?(时间复杂度:O(n lg k))

4. 总结

堆是一种非常基础但很实用的数据结构,很多复杂算法或者数据结构的基础就是堆,因而,了解和掌握堆这种数据结构显得尤为重要。

5. 参考资料

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


    
 
 

您可能感兴趣的文章:

  • 数据结构之位图(bitmap)详解
  • 数据结构之Treap详解
  • 数据结构课程设计- 解析最少换车次数的问题详解
  • 数据结构之AVL树详解
  • 数据结构课程设计-用栈实现表达式求值的方法详解
  • 数据结构之伸展树详解
  • 数据结构之红黑树详解
  • python实现bitmap数据结构详解
  • Python常见数据结构详解
  • 解析从源码分析常见的基于Array的数据结构动态扩容机制的详解
  • <<大话数据结构>>中冒泡排序算法改进
  • 请问:在用proc方式往数据库插入数据时,我能不能定义一个结构体,它与表的每一项对应,将结构体赋好值后,再只将这个结构体插入表中,这行不行啊?
  • 基于Key-Value的NOSQL数据库Redis的数据结构及常用相关命令介绍
  • 强人,linux下驱动相关数据结构和usb设备数据结构之间的功能分析
  • Oracle数据库(Oracle Database)体系结构及基本组成介绍
  • GNU汇编fill填充一个数据结构使得另一个数据结构全部清零
  • 数据结构:图(有向图,无向图),在Python中的表示和实现代码示例
  • 高手帮帮忙!vi中如何实现跳转到任意结构体或函数的声明处,包括系统库中声明的函数和数据结构?
  • mysql 命令大全及导入导出表结构或数据
  • 协议的设计一般采用结构体进行数据打包,在协议设计的结构体中能不能使用指针 ?
  • 通用数据结构库 GDSL
  • 如何把一个数组转化为一个数据结构,如ArrayList。
  • 多维数据结构 mdds
  • sem_t的数据结构是什么?
  • C数据结构库 liblfds
  • 一个新的JavaScript数据结构 stream.js
  • 数据结构和算法教程 OpenDSA
  • 数据结构
  • 请教各位,数据结构在工程中到底有什么应用呢
  • 放假了,想用java数据结构,请问大虾们该如何开始?
  • 数据结构库 libx1f4l2
  •  
    本站(WWW.)旨在分享和传播互联网科技相关的资讯和技术,将尽最大努力为读者提供更好的信息聚合和浏览方式。
    本站(WWW.)站内文章除注明原创外,均为转载、整理或搜集自网络。欢迎任何形式的转载,转载请注明出处。












  • 相关文章推荐
  • 请教:请问java中存放数据库中的记录,用什么数据结构?(hashtable?vector?还是别的?)
  • 看LINUX的内核要不要硬件、数据结构、算法、汇编
  • 请教JAVA中的数据结构
  • 常用数据结构库 sundial
  • 基于测试nginx数据结构的开源库 libngx
  • 数据结构算法库 DSAL
  • 哪里有《数据结构与算法分析(JAVA版)》的电子书下载,谢了:)
  • 那个大侠可以推荐一本关于java的数据结构和算法的书?  
  • 请大家推荐几本关于数据结构的书。
  • 一个可以自动排序、频繁增删的队列,采用哪种数据结构比较好?
  • “堆”和“栈”是有区别的数据结构,为什么很多书中都将它们放在一起使用呢?
  • 请问哪里有《数据结构与算法分析(JAVA版)》的电子书下载????
  • 求救!!!!关于(数据结构(java版)王国瑜/叶乃菁 编著)
  • 在头文件中,数据结构怎么写
  • 请问有关linux底层网络数据结构sk_buff相关知识
  • 请问哪里有比较全的Linux内核编程API和数据结构的文档?
  • 文件描述符的数据结构在哪定义?
  • 文本编辑器数据结构
  • 手把手教你Oracle数据库导出数据库结构到PowerDesigner
  • tslib数据结构的问题


  • 站内导航:


    特别声明:169IT网站部分信息来自互联网,如果侵犯您的权利,请及时告知,本站将立即删除!

    ©2012-2021,,E-mail:www_#163.com(请将#改为@)

    浙ICP备11055608号-3