关于数据结构:数据结构-堆

48次阅读

共计 1112 个字符,预计需要花费 3 分钟才能阅读完成。

简介

概念

堆是一种比拟非凡的数据结构,它用数组实现的二叉树,并且总是满足以下性质:

  • 堆总是一棵齐全二叉树
  • 堆中某个结点总是不大于或不小于其父结点的的值

属性

堆分为两种:根结点最大的堆叫作 最大堆 大根堆 ;根结点最小的堆叫作 最小堆 小根堆

堆属性十分有用,其使得堆经常被当做优先队列应用,因为能够疾速地拜访到“最重要”的元素。

堆和二叉搜寻树的区别

堆并不能取代二叉搜寻树,它们之间有相似之处也有一些不同。两者的次要区别如下:

属性二叉搜寻树
结点的程序在最小堆中父结点必须比子结点小,在最大堆中父结点必须比子结点大,变动是从上到下左子结点比父结点小,父结点比右子结点小,变动是从左到右
内存占用应用数组作为底层存储构造,占用内存空间较小应用链表作为底层存储构造,占用内存空间较大
均衡不须要整棵树有序必须是均衡的,总体上是有序的
搜寻搜寻很慢搜寻很快

堆的实现

存储

实现一个堆,首先是波及到如何存储一个堆。

依据堆总是一棵齐全二叉树的性质,以及齐全二叉树比拟适宜用数组来存储的概念,能够晓得用数组存储堆是比拟好的抉择。

从上图能够看到,数组中下标为 i 的结点的左子结点,就是下标为 2i 的结点,右子结点就是下标为 2i + 1 的结点,父结点就是下标为 i/2 的结点。

堆化

往堆中插入或者删除一个元素后,重要的是须要持续满足堆的两个个性,而这个从新满足堆个性的过程称为 堆化

堆化实际上有两种:从下往上、从上往下。

插入元素

插入元素时波及的是从下往上的堆化办法。

往堆中插入一个元素其实就是往底层数组的开端增加元素,上面是示例图:

从下往上堆化的过程比较简单,实际上就是将插入的元素与父结点进行比拟,呈现不合乎个性的状况就调换两个结点,始终反复这个过程,直至父子结点之间满足堆的个性。

删除元素

从堆的个性能够看出,堆顶元素存储的就是堆中数据的最大值或最小值。

当删除堆顶元素的时候,为放弃堆的个性,则会波及到从上往下的堆化办法。

从上往下堆化不是间接从堆顶元素开始与子结点进行调换,而是先将数组中的最初一个元素移到被删除结点地位(为了满足齐全二叉树的个性),而后利用同样的父子结点比对办法。

通常,对于大根堆会比拟较大的子结点,对于小根堆会比拟较小的子结点,呈现不合乎个性的状况就调换两个结点,始终反复这个过程,直至父子结点之间满足堆的个性。

这种办法堆化之后的后果,必定满足齐全二叉树的个性。

复杂度

一个蕴含 n 个节点的齐全二叉树,树的高度不会超过 $\log_2n$。

堆化的过程是顺着节点所在门路比拟替换的,所以堆化的工夫复杂度跟树的高度成正比,也就是 $O(\log n)$。

插入数据和删除堆顶元素的次要逻辑就是堆化,所以往堆中插入一个元素和删除堆顶元素的工夫复杂度都是 $O(\log n)$。

正文完
 0