heapSort1和heapSort2的不同

Question

我认为heapSort1比heapSort2慢的原因，是因多了一个maxheap.insert函数，但是insert中存在一个向上排序（shiftUp函数），在插入完成后，也就意味着已经排序，成为最小堆，再进行一次最大堆的排序。

要是在insert函数中，取消‘’shiftUp(count+1)‘’，直接插入一个无序的，直接用shiftDown排序。

与heapSort2算法的效率的差异，是否存在此处？

void insert(Item item){
        assert( count + 1 <= capacity );
        data[count+1] = item;
        //shiftUp(count+1);
        count ++;
    }

4-5 基础堆排序和Heapify 中的疑问。请老师解答一下 @liuyubobobo

Answer 1

liuyubobobo 2016-12-18 20:25:10

我们可以看到heapSort1的代码：

template<typename T>    
void heapSort1(T arr[], int n){
    // 创建最大堆    
    MaxHeap<T> maxheap = MaxHeap<T>(n);    
    for( int i = 0 ; i < n ; i ++ )    
        maxheap.insert(arr[i]);    
    
    // 逐渐取出最大元素
    for( int i = n-1 ; i >= 0 ; i-- )    
        arr[i] = maxheap.extractMax();    
}

和heapSort2的代码：

template<typename T>    
void heapSort2(T arr[], int n){  
    // 创建最大堆  
    MaxHeap<T> maxheap = MaxHeap<T>(arr,n);    
    
    // 逐渐取出最大元素
    for( int i = n-1 ; i >= 0 ; i-- )    
        arr[i] = maxheap.extractMax();    
}

 

后面一部分是相同的，都使用了这样的循环：

for( int i = n-1 ; i >= 0 ; i-- )    
    arr[i] = maxheap.extractMax();

在这个循环中，我们不断利用maxheap的性质取出最大的元素，完成了对整个数组的排序。所以，两种方法不同的地方在于是如何创建的最大堆。如果你将insert中的shiftUp操作删除，则第一种算法的第一部分无法创建一个最大堆。第二部分的操作就是错误的。我没有特别理解你说的“直接用shiftDown排序”是什么意思。事实上，heapSort2的MaxHeap<T>(arr,n); 就隐含了ShiftDown操作。我们在4-6介绍的原地堆排序，原理和heapSort2类似，也是不断的使用shiftDown完成堆排序。如果你说的是这个意思，恭喜你，你直接找到了一个更优的解决方案：）

在这里，我主要想向大家介绍的一个有意思的事实是，heapSort1和heapSort2中两种创建堆的方式，他们的复杂度是不一样的。heapSort1中逐渐将元素插入到堆中的方式，其时间复杂度是O(nlogn)的；但是heapSort2中反向从第一个非叶子节点倒序不断ShiftDown的过程，最终也创建了一个堆，但是其时间复杂度是O(n)的。这背后的数学推倒比较复杂，在课程中我只提了一嘴，使用实验的方式向大家展示了这个区别。有兴趣的同学，可以查阅更多资料学习一下：） 

• 提问者 小叶柏杉 #1

  非常感谢！

Answer 2

Penguinbupt 2017-04-23 17:05:08

你说的直接插入insert无序的，然后在shiftDown。

这就是第二种排序方式嘛，第二种方式是直接给一个无序的数组，从n/2至1进行shiftDown操作进行建堆。