java在存储数组时栈内存和堆内存的联系是什么？

Python018

java在存储数组时栈内存和堆内存的联系是什么？,第1张

堆和栈都是一种数据项按序排列的数据结构。

（1）栈就像装数据的桶或箱子：它是一种具有后进先出性质的数据结构，也就是说后存放的先取，先存放的后取。这就如同要取出放在箱子里面底下的东西（放入的比较早的物体），首先要移开压在它上面的物体（放入的比较晚的物体）。

（2）堆像一棵倒过来的树：堆是一种经过排序的树形数据结构，每个结点都有一个值。通常所说的堆的数据结构，是指二叉堆。堆的特点是根结点的值最小（或最大），且根结点的两个子树也是一个堆。由于堆的这个特性，常用来实现优先队列，堆的存取是随意，这就如同在图书馆的书架上取书，虽然书的摆放是有顺序的，但是想取任意一本时不必像栈一样，先取出前面所有的书，书架这种机制不同于箱子，可以直接取出想要的书。

    优先队列更多的是一种逻辑上和业务上的设计。队列中的每项元素都分配一个优先权值，队列的出队顺序按照优先权值来划分，高优先权先出队或者低优先权先出队。这样一个优先队列必须具备两个最基本的操作——入队，以及高(低)优先权出队。优先队列在很多场景中都有运用，比如打印机的任务调度和操作系统中的进程调度都有用到优先队列的设计。

    此时我们假设并不知道有堆这样的数据结构，想实现上述这样的功能，其实也可以有多种解决方案，比如以下两种：

    二叉堆如其名字一样和二叉树具有紧密的关系。二叉堆是一种特殊的二叉树，是对一般的二叉树提出了结构性和堆序性的要求，这种特殊结构性和堆序性是二叉堆的性质所在。

1.结构性：二叉堆是一个完全二叉树

2.堆序性：所有的节点值均小于(大于)其后裔节点值，若所有节点值大于其后裔节点这样的二叉堆称为大根堆##点值均小于其后裔节点这样的二叉堆成为小根堆。

    这里可以看到，假如是小根堆的情况，那么每次取堆顶的元素，就完成了按低优先级出队的功能。若是大根队取堆顶的元素则完成按高优先级出对的顺序。

    这里需要特别注意就是，每次的出队操作=返回堆顶元素+删除堆顶元素，每次删除堆顶元素之后，需要保证依旧满足二叉堆的结构性和对堆序性，这个删除和调整的过程称为堆调整。

    下面以大根堆为例进行介绍一次堆调整，并且分析其时间复杂度为什么是O(logN)。下文描述中，堆的删除操作=优先队列的出队，堆的插入操作=优先队列的入队。

    上文介绍了大根堆的出队操作，其时间复杂度在O(logN),此处介绍大根堆的入队操作，入队操作和出队操作和其相似，最坏时间复杂度也是O(logN)。下面将通过图例的形式分析大根堆的入队操作，假设插入元素是19。

2.如图9所示，在插入元素之后二叉堆的结构特性已经满足了，下面主要需要调整堆序特性。对于元素19而言，找到其父亲元素8，判断堆序性，发现19大于8，所以交换19和8的位置，结果如下。

Reference:

[1] 数据结构与算法 java语言描述版

[2] 博客原文