shiftUp、shiftDown及heapify的区别？？？
来源：4-5 基础堆排序和Heapify
Penguinbupt
2017-04-23
我的问题如下：
shiftDown其实是不是就是heapify操作？？？
shiftUp也算是一种heapify的操作？？？只不过shiftUp用于插入，而不用于建堆。
我写了一个shiftUp2，同样能达到排序的功能，但排序时间慢得多。
void shiftUp2(int k)
{
for(int i=k/2;i>=1;i--)
{
shiftDown(i);
}
}
是不是由于shiftUp是直接上升的每层调整一个元素，而shiftUp2是一层一层的来扫描，其实在另一颗子树根本无需扫描，只仅仅调整插入数值的那颗子树即可。
我的思路：
您的代码shiftUp、shiftDown、heapify均是迭代的方式，而算法导论中 第86页的heapify使用了递归的方式。
这个heapify仅仅对 i 、left(i)、right(i)这三个数进行调整，然后递归或者迭代下去，而不是将整过程称作heapify。
在4-4中的shiftDown是extractMax函数提取最大数后的一个恢复堆的一种迭代操作，只不过这时候 除了根节点不满足堆而左右子树是正常的，所以仅仅对根节点进行heapify操作即可。
而在后续的建堆的过程中，heapify从n/2开始至1，是假设叶子节点都是堆。
你的代码里面的调整就是shiftDown，让我觉得和算法导论相对比较，就感觉shiftDown就是heapify操作。
shiftDown==heapify
2回答
-
我看了一下算法导论的相关章节。它对函数的名称和定义确实和我的是不一样的。
6.2小节的Max-Heapify(A,i)就是我的课程里的shiftDown，是对一个元素i在做事情，调整堆中索引为i的元素将这个元素向下调整到合适的位置。
6.3小节的Build-Max-Heap(A)就是我课程里的heapify，操作对象是一整个数组，将一个原本无序的数组调整成一个堆结构。
6.5小节的Heap-Increase-Key(A, i, key)相当于我课程里的shiftUp，调整堆中索引为i的元素将这个元素向上调整到合适的位置。只不过课程里将这个元素赋值放在了insert中，在算法导论里，这个Heap-Increase-Key既负责了赋值，又负责了上调过程：）
10 -
liuyubobobo
2017-04-24
shiftUp(k) 是调整堆中索引为k的元素将这个元素向上调整到合适的位置。
shiftDown(k) 是调整堆中索引为k的元素将这个元素向下调整到合适的位置。
上面这两个函数都是针对堆中某一个具体元素的调整你可以看到shiftUp被使用在向堆中添加一个元素以后再调整这个元素的位置shiftDown被使用在从堆中取出一个元素后再将堆中的最后一个元素放到堆顶以后调整这个堆顶元素。
heapify不同。heapify的操作对象是一整个数组。他的作用是将一个原本无序的数组调整成一个堆结构。heapify的过程借助了shiftDown来调整堆中的一个个具体元素。heapify的过程核心就是这个循环
for( int i = count/2 ; i >= 1 ; i -- ) shiftDown(i);
实际就是自底向上对堆中的所有非叶子节点使用shiftDown进行调整的过程
212017-04-24
相似问题