动力节点旗下在线教育品牌  |  咨询热线:400-8080-105 学Java全栈,上蛙课网
首页 > 文章

数据结构中的堆

07-01 17:50 182浏览
举报 T字号
  • 大字
  • 中字
  • 小字

有一种非常灵活又特殊的数据结构,我们可以单独地使用它来解决很多有趣的问题。而且这种数据结构的的定义本来就有最优的含义,所以它与贪心算法有着天然的联系。它的本质是一个完全二叉树。它的身份也就呼之欲出了,它就是数据结构中

堆这种数据结构可以被看做一棵完全二叉树的数组对象。通过分析,我们可以使用数组来实现它。由于堆本质上是一棵完全二叉树,因此,这里可以直接使用二叉树的相关概念,例如高度等等。在实现二叉树的时候,树结点通常这样定义:

public class Node {

    public T data;

    public Node left;

    public Node right;

    public Node parent;

    public int state;

 

    public Node(T d) {

        this.data = d;

    }

}

也就是说,一个结点通常会有左,右孩子结点指针和父结点指针。但在完全二叉树中,是可以省略掉这三个指针的,因为完全二叉树的结点编号都是有规律的。给定某一个结点,假设它的下标为i,那么它的左孩子结点的下标就是2i + 1,右孩子结点的下标就是2i + 2,它的父结点为(i−1)/2。这样,我们就把可以省略去这些指针,直接将堆中的结点存储在数组中了。

堆又分为最大堆和最小堆。将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。堆的性质非常简单,如果是最大堆,对于每个结点,都有结点的值大于两个孩子结点的值。如果是最小堆,那么对于每个结点,都有结点的值小于孩子结点的值。堆是非线性数据结构,相当于一维数组,有两个直接后继。

对于一个堆,如果除了堆顶元素不满足结点大于孩子结点的条件,它的两个子树已经是符合条件的最大堆,我们很容易就可以将其再维护成一个符合条件的最大堆。将堆顶元素与两个孩子结点中最大的那个进行交换,然后再对互换的子树递归地进行维护。这就是一个建堆的过程。

    public static void maxHeapify(int arr[], int length, int root) {

        if (root >= length) {

            return;

        }

 

        int largest = root;

        int left = root * 2 + 1;

        int right = root * 2 + 2;

 

        if (left < length && arr[left] < arr[largest]) {

            largest = left;

        }

 

        if (right < length && arr[right] < arr[largest]) {

            largest = right;

        }

 

        if (largest != root) {

            int t = arr[root];

            arr[root] = arr[largest];

            arr[largest] = t;

 

            maxHeapify(arr, length, largest);

        }

    }

有了规范化最大堆的函数以后,我们就可以轻松地从把一个无序数组规范化成一个堆。首先,如果堆中只含有一个元素,那么它必然是一个规范的最大堆,也就是说,如果把一个数组表示成完全二叉树,那么树上的每一个叶子结点都是一个规范的最大堆。这样,我们可以不断地自底向上规范化子堆,直到整个堆已经全部规范化。

    public static void buildUpHeap(int[] arr) {

        if (arr.length <= 1)

            return;

 

        int n = (arr.length - 2) / 2;

 

        while (n >= 0) {

            maxHeapify(arr, arr.length, n);

            n--;

        }

    }

我们讲的方法是自底向上地建堆。这种方法应用于堆排序可以减少空间的使用,但其实不利于扩展。与之相对的,还有一种自上而下的建堆方法,这里就不多做介绍了。

在程序中,堆用于动态分配和释放程序所使用的对象。在以下情况中调用堆操作:

1.事先不知道程序所需对象的数量和大小。

2.对象太大,不适合使用堆栈分配器。

堆使用运行期间分配给代码和堆栈以外的部分内存。

传统上,操作系统和运行时库随附了堆实现。当进程开始时,操作系统创建称为进程堆的默认堆。如果没有使用其他堆,则使用进程堆分配块。语言运行时库也可在一个进程内创建单独的堆。(例如,C 运行时库创建自己的堆。)除这些专用堆外,应用程序或许多加载的动态链接库 (DLL) 之一也可以创建并使用单独的堆。Win32 提供了一组丰富的 API用于创建和使用专用堆。有关堆函数的优秀教程,请参阅 MSDN 平台 SDK 节点。

当应用程序或 DLL 创建专用堆时,这些堆驻留于进程空间中并且在进程范围内是可访问的。某一给定堆分配的任何数据应为同一堆所释放。(从一个堆分配并释放给另一个堆没有意义。)

在所有虚拟内存系统中,堆位于操作系统的虚拟内存管理器之上。语言运行时堆也驻留在虚拟内存之上。某些情况下,这些堆在操作系统堆的上层,但语言运行时堆通过分配大的块来执行自己的内存管理。绕开操作系统堆来使用虚拟内存函数可使堆更好地分配和使用块。典型的堆实现由前端分配器和后端分配器组成。前端分配器维护固定大小块的自由列表。当堆收到分配调用后,它尝试从前端列表中查找自由块。如果此操作失败,则堆将从后端(保留和提交虚拟内存)分配一个大块来满足请求。通常的实现具有每个块分配的开销,这花费了执行周期,也减少了可用存储区。

单个全局锁可防止多线程同时使用堆。此锁主要用于保护堆数据结构不受多线程的任意访问。当堆操作过于频繁时,此锁会对性能造成负面影响。

堆在数据结构中有着特殊的地位,不是一时半会儿就能完全说的清楚的。想更深层次了解数据结构中相关知识的可以在我们的网站中查看相关课程,格物致知方是求学之本。

1人推荐
共同学习,写下你的评论
0条评论
上善若水
程序员上善若水

16篇文章贡献85593字

作者相关文章更多>

推荐相关文章更多>

Java数据结构

HelloWorld10-31 08:24

浅谈MySQL中SQL优化的常用方法

军哥08-12 23:29

五分钟读懂UML类图

江湖人称小李白12-10 10:41

MyBatis开发框架的四大核心

IT逐梦者08-17 21:43

一次搞定continue,break和return

HelloWorld11-06 11:19

发评论

举报

0/150

取消