数据结构--堆的向上调整和向下调整

1.完全二叉树

下面的这个就是对于我们的完全二叉树的这个逻辑结构和物理结构的说明：

逻辑结构就是我们自己认为的进行购想出来的；

但是这个物理结构却是我们的这个数据结构在内存里面的真是进行存储的这个形态的一个体现；

1）通过下面的这个图片，我们首先需要知道这个完全二叉树的定义，其实下面的这个实例很特殊，它既是一个完全二叉树，也是一个满二叉树；

2）我们的这个完全二叉树它的定义就是他的这个所有的节点进行编号和我们的这个满二叉树是一样的，这个时候我们就把这个树称之为完全二叉树；

3）下面的这个满二叉树实际上就是一个完全二叉树；

4）我们可以看到这个完全二叉树在我们的这个内存里面实际上是使用这个数组进行存储的，但是我们在学习这个数据结构的时候，使用的是他的逻辑结构，也就是二叉树；

2.堆向上调整

这个主要是我们的建堆的过程，就是我们进行建堆的时候，这个数据从我们的叶子结点开始需要进行这个向上调整的过程；

我们从上面的这个建堆的过程是可以看到的，他是需要和自己的这个父亲节点不断地进行比较，直到他的数值比父亲节点的数值小，这个大堆才完成；

我们的建堆主要是在下面的这个插入数据的过程里面使用的：我们首先就是进行的这个空间的开辟，最后是调用我们的这个向上调整的函数，这个就是说：我们的这个向上调整就是进行插入的时候保证我们的这个大堆的结构（就是我们插入数据之后，他还是一个堆）；
下面的这个：我们的这个child参数就是我们插入的数据，我们的这个函数就是对于这个数据的位置进行调整，使用这个父子节点的关系，我们根据这个子节点的小标，找到这个parent节点的大小；

如果我们的这个儿子数值比我们的这个父亲大，这个时候就是需要向上进行调整的，我们的这个调整的方法就是先交换，交换之后让我们的这个儿子向上走（也就是代码里面的这个child=parent);

我们的这个child向上之后，这个对应的这个parent也就是需要发生变化的，这个变化就是把我们的这个child-1/2之后的值作为新的这个parent节点的下标；

我们如何去验证这个调整的结果是否正确：我们去进行这个堆的初始化，向这个里面进行我们的数据的插入，这个时候断掉调试，hp.a,6----这个就会显示我们的这个数组里面的6个元素的位置，我们根据这个调试的结果做出来这个对应的树，这个时候发现我们插入数据之后，这个最后的解构就是一个大根堆（如图所示）；

3.堆向下调整

这个向下调整是如何引出来的，就是我们的这个数据进行插入之后，这个时候我们的大堆的结构就形成了，这个时候我们的这个父亲节点肯定就是最大的这个元素，这个时候，我们的处理就是想要知道这个第二大的元素（这个过程实际上就是我们堆排序的雏形，但是这个并不是真正的堆排序）；

我们去掉这个父亲节点之后，想要直到这个第二大的元素是哪一个，并且去掉这个父亲节点之后的这个树的结构又是什么样子的，这个时候有些人的方案就是：

1）这个完全二叉树不就是一个数组吗，我们的这个父亲节点就是这个数组里面的第一个元素，这个时候我们直接把这个后面的所有的元素向前移动不就可以了；

2）但是上面的这个方案是不可取的，主要是因为我们如果使用上面的这个方式进行调整，我们的这个数据之间的这个父子关系就完全发生了变化，因此我们否定这个解法；

3）正确的解法就是我们让这个父亲节点和我们的这个最后的这个节点进行交换，直接使用我们的这个pop删除这个最后的元素，这个时候原本的最后的一个元素放到了根节点的位置，其他的所有的元素的位置都是不变的，这样可以维持我们的这个数据之间的这个父子的关系；

4）但是现在他是不符合我们的大根堆的定义的，因此这个时候我们的处理就是让这个元素向下进行比较，不断的向下调整-----------这个就是我们的向下调整的这个出现的场景；

下面的这个就是我们进行pop操作的时候，我们需要交换之后size–就可以了，然后我们对于这个时候的0下标的位置的元素向下调整；

这个时候我们的方法就是需要找到这个时候的两个儿子里面的最大的那个元素：也就是和我们的这个父亲节点相邻的两个孩子，找到他们里面的较大的一个，如果我们比这两个里面的较大的一个小，这个时候我们就是需要进行调整的，这个里面的child+1<N是为了防止越界;

这个while控制的是我们的这个比较的过程是不是到达了根节点，第一个if是默认我们的这个左边的孩子是最大的，如果发现是这个右边的比左边的大，我们的这个child++，同时如果出现了这个只有左边的孩子，没有右边的孩子，这个时候child+1就会越界，因此我们使用这个child+1防止越界；

下面的这个就是我们的4和17里面的这个较大的就是17，因此我们的这个3就需要和我们的17进行比较，这个时候发现是不满足我们的这个大根堆的定义的，因此这个就需要向下调整：

child的值赋值给我们的parent,这个时候新的child就是我们这个时候的parent*2+1即可；

4.测试代码

这个时候，我们既可以随机的插入数据，打印这个大堆的结果；

我们也可以插入很多的数据，使用这个k限制，打印出来有限多个数据，两个方式都是可以的；

这个时候，我们既可以随机的插入数据，打印这个大堆的结果；

我们也可以插入很多的数据，使用这个k限制，打印出来有限多个数据，两个方式都是可以的；

原文地址：https://blog.csdn.net/binhyun/article/details/144635875

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！