Python 堆排序：如何排序？

Heap Sort: how to sort?

提问by I159

I'm trying to implement Heap Sort in Python, but I can't seem to get it right. I've tried to implement this pseudo code, but my code does not sort! It just sifts to ridiculous effect. I'm inclined to think that the problem is in this line:

我正在尝试在 Python 中实现堆排序，但我似乎无法正确实现。我试图实现这个伪代码，但我的代码没有排序！它只是筛选到可笑的效果。我倾向于认为问题出在这一行：

swap the root(maximum value) of the heap with the last element of the heap

将堆的根（最大值）与堆的最后一个元素交换

How do I get the maximum value?

我如何获得最大值？

That is what I have:

这就是我所拥有的：

def my_heap_sort(sqc):                    
    def heapify(count):                
        start = (count-2)/2            
        while start >= 0:              
            sift_down(start, count-1)  
            start -= 1                 

    def swap(i, j):                    
        sqc[i], sqc[j] = sqc[j], sqc[i]

    def sift_down(start, end):         
        root = start                   

        while (root * 2 + 1) <= end:   
            child = root * 2 + 1       
            temp = root                
            if sqc[temp] < sqc[child]: 
                temp = child+1         
            if temp != root:           
                swap(root, temp)       
                root = temp            
            else:                      
                return                 

    count = len(sqc)                   
    heapify(count)                     

    end = count-1                      

    while end > 0:                     
        swap(end, 0)                   
        end -= 1                       
        sift_down(0, end)              

And I found an example with almost the same problem:

我发现了一个几乎同样问题的例子：

def heap_sort_example(a):                                 
    def heapify(a):                                       
        start = (len(a) - 2) / 2                          
        start -= 1                                        

    def sift_down(a, start, end):                         
        root = start                                      
        while root * 2 + 1 <= end:                        
            child = root * 2 + 1                          
            if child + 1 <= end and a[child] < a[child+1]:
                child += 1                                
            if child <= end and a[root] < a[child]:       
                a[root], a[child] = a[child], a[root]     
                root = child                              
            else:                                         
                return                                    

    heapify(a)                                            
    end = len(a) - 1                                      
    while end > 0:                                        
        a[end], a[0] = a[0], a[end]                       
        sift_down(a, 0, end-1)                            
        end -= 1                                          

The results are different, but both are ridiculous:

结果虽然不同，但都是可笑的：

>>> my_heap_sort(sqc)
[2, 7, 1, -2, 56, 5, 3]

>>> heap_sort_example(sqc)
[-2, 1, 7, 2, 56, 5, 3]

采纳答案by I159

I found it and almost figured how it works:

我找到了它，几乎想通了它是如何工作的：

def heapsort(sqc):                                 
    def down_heap(sqc, k, n):                            
        parent = sqc[k]                                  

        while 2*k+1 < n:                                 
            child = 2*k+1                                
            if child+1 < n and sqc[child] < sqc[child+1]:
                child += 1                               
            if parent >= sqc[child]:                     
                break                                    
            sqc[k] = sqc[child]                          
            k = child                                    
        sqc[k] = parent                                  

    size = len(sqc)                                      

    for i in range(size/2-1, -1, -1):                    
        down_heap(sqc, i, size)                          

    for i in range(size-1, 0, -1):                       
        sqc[0], sqc[i] = sqc[i], sqc[0]                  
        down_heap(sqc, 0, i)                             

edit:

编辑：

This implementation is written based on my own understanding of the algorithm. It is longer, but to me this algorithm is much clearer in this implementation. Long naming is help when you need to understand the algorithm, so I left intact all the long names.

这个实现是根据我自己对算法的理解编写的。它更长，但对我来说，这个算法在这个实现中更加清晰。当你需要理解算法时，长命名是有帮助的，所以我保留了所有的长名称。

def heapsort(sequence):                                                      
    sequence_length = len(sequence)                                          

    def swap_if_greater(parent_index, child_index):                          
        if sequence[parent_index] < sequence[child_index]:                   
            sequence[parent_index], sequence[child_index] =\                 
                    sequence[child_index], sequence[parent_index]            

    def sift(parent_index, unsorted_length):                                 
        index_of_greater = lambda a, b: a if sequence[a] > sequence[b] else b
        while parent_index*2+2 < unsorted_length:                            
            left_child_index = parent_index*2+1                              
            right_child_index = parent_index*2+2                             

            greater_child_index = index_of_greater(left_child_index,         
                    right_child_index)                                       

            swap_if_greater(parent_index, greater_child_index)               

            parent_index = greater_child_index                               

    def heapify():                                                           
        for i in range((sequence_length/2)-1, -1, -1):                       
            sift(i, sequence_length)                                         

    def sort():                                                              
        count = sequence_length                                              
        while count > 0:                                                     
            count -= 1                                                       
        swap_if_greater(count, 0)                                        
        sift(0, count)                                                   

    heapify()                                                                
    sort()                                                        

edit:

编辑：

And optimized version:

和优化版本：

def opt_heapsort(s):                               
    sl = len(s)                                    

    def swap(pi, ci):                              
        if s[pi] < s[ci]:                          
            s[pi], s[ci] = s[ci], s[pi]            

    def sift(pi, unsorted):                        
        i_gt = lambda a, b: a if s[a] > s[b] else b
        while pi*2+2 < unsorted:                   
            gtci = i_gt(pi*2+1, pi*2+2)            
            swap(pi, gtci)                         
            pi = gtci                              
    # heapify                                      
    for i in range((sl/2)-1, -1, -1):              
        sift(i, sl)                                
    # sort                                         
    for i in range(sl-1, 0, -1):                   
        swap(i, 0)                                 
        sift(0, i)                                 

回答by locojay

selection sort is a relatively straight forward sorting algorithm: traverse an array, extract the minimun of the first n elements , then extract min of the next n-1 elements ...... Now this would be O(n^2) algorithm.

选择排序是一种相对直接的排序算法：遍历数组，提取前 n 个元素的最小值，然后提取接下来的 n-1 个元素的最小值......现在这将是 O(n^2) 算法.

Since you are always extracting a min you should think of using a minimum Heap. it extracts a min in O(log n) time. extracting the min n times leads to O(n*log n) time.

由于您总是在提取 min，因此您应该考虑使用最小堆。它在 O(log n) 时间内提取一分钟。提取最小 n 次导致 O(n*log n) 时间。

so for heap sort one just needs to build a heap (heapify O(n)) and the traverse the array and extract the min n times.

所以对于堆排序，只需要构建一个堆（堆化 O(n)）并遍历数组并提取最小 n 次。

you can use the python heapto build a heap or build your own.

您可以使用 python堆构建堆或构建自己的堆。

def heapsort(l):
    hp = make_heap(l)
    for i in range(len(l)):
       yield hp.extract_min() 

回答by Skyler

How do I get the maximum value?You don't need to "get" it. The root is exactly the maximum, that's a defined property of a heap.

我如何获得最大值？你不需要“得到”它。根正好是最大值，这是堆的定义属性。

If you feel tough to understand heap sort, this chapterwill be extremely helpful.

如果您觉得难以理解堆排序，本章将非常有帮助。

---

---

I rewrote your code:

我重写了你的代码：

def swap(i, j):                    
    sqc[i], sqc[j] = sqc[j], sqc[i] 

def heapify(end,i):   
    l=2 * i + 1  
    r=2 * (i + 1)   
    max=i   
    if l < end and sqc[i] < sqc[l]:   
        max = l   
    if r < end and sqc[max] < sqc[r]:   
        max = r   
    if max != i:   
        swap(i, max)   
        heapify(end, max)   

def heap_sort():     
    end = len(sqc)   
    start = end // 2 - 1 # use // instead of /
    for i in range(start, -1, -1):   
        heapify(end, i)   
    for i in range(end-1, 0, -1):   
        swap(i, 0)   
        heapify(i, 0)   

sqc = [2, 7, 1, -2, 56, 5, 3]
heap_sort()
print(sqc)

It gives:

它给：

[-2, 1, 2, 3, 5, 7, 56]  

回答by BeMeCollective

I find that the different implementations of heapify, the "heart" of heap sort are not clear on the internetz. Here is my humble attempt to help the community by adding a simple but clear example of "heapify". I use vectors to avoid the extra confusion of array manipulation.

我发现heapify的不同实现，堆排序的“心脏”在internetz上不清楚。这是我通过添加一个简单但清晰的“heapify”示例来帮助社区的谦虚尝试。我使用向量来避免数组操作的额外混淆。

This method heapifies 1 cell of the array. To heapify the whole array you need a loop, run it from middle of array, moving to beginning. The returned vector MUST be the same one we send in the next iteration, otherwise it's a mess. eg:

此方法堆化数组的 1 个单元格。要堆化整个数组，您需要一个循环，从数组中间运行它，移动到开头。返回的向量必须与我们在下一次迭代中发送的向量相同，否则会一团糟。例如：

for (int i = myvector.size()/2; i >= 0; i--) { in = Heapify(in, i);}

vector_of_int Sort::Heapify(vector_of_int in_vector, int in_index)
{

int min_index = in_index; // Track index of smallest out of parent and two children.
int left_child_index = 0; 
int right_child_index = 0;
int vector_size = in_vector.size(); 

left_child_index = LeftChildIndex(in_index);// index of left child, at position 2*in_index
right_child_index = left_child_index + 1;// index of right child, at position 2*in_index + 1

// If left_child_index is not overflowing, suggest swap...
if ((left_child_index) < vector_size) 
{
    // If parent larger than left child, min_index remembers left child position
    if (in_vector[min_index] > in_vector[left_child_index]) 
    { min_index = left_child_index; }
}

// If right_child_index is is not overflowing, suggest swap...
if (right_child_index < vector_size) 
{
    // If parent larger than right child, min_index remembers right child position
    if (in_vector[min_index] > in_vector[right_child_index]) 
    { min_index = right_child_index; }
}

// Now min_index has the index of the smallest out of parent and it's two children.
// If the smallest is not the parent, swap parent and smallest.
if (min_index != in_index) 
{
    in_vector = swap(in_vector, in_index ,min_index);
    in_vector = Heapify(in_vector, min_index); // RECURSION IS HERE
}

return in_vector;
}
// End heapify

回答by user2490585

Heap sort example with example of how to initially build a heap

堆排序示例以及如何初始构建堆的示例

def findMin(heapArr,i,firstChildLoc,secondChildLoc):
        a = heapArr[i]
        b = heapArr[firstChildLoc]
        c = heapArr[secondChildLoc]
        return i if ((a < b) and (a < c)) else firstChildLoc if (b < c) else secondChildLoc


def prelocateUp(heapArr):
    l = len(heapArr)
    i = l-1
    while True:
        parentLoc = (i+1)/2 - 1 
        if parentLoc >= 0:
            if heapArr[parentLoc] > heapArr[i]:
                temp = heapArr[parentLoc]
                heapArr[parentLoc] = heapArr[i]
                heapArr[i] = temp  
        else :
            break
        i = parentLoc
    return heapArr

def prelocateDown(heapArr):

    l = len(heapArr)
    i = 0

    while True:
        firstChildLoc = 2*(i+1) - 1
        secondChildLoc = 2*(i+1)
        if (firstChildLoc > l-1):
            break

        elif (secondChildLoc > l-1):
            if heapArr[i] > heapArr[firstChildLoc]:
                temp = heapArr[i]
                heapArr[i] = heapArr[firstChildLoc]
                heapArr[firstChildLoc] = temp
            break

        else :
            minLoc = findMin(heapArr,i,firstChildLoc,secondChildLoc)
            if minLoc !=i:
                temp = heapArr[i]
                heapArr[i] = heapArr[minLoc]
                heapArr[minLoc] = temp
                i = minLoc
            else :
                break
    return heapArr



def heapify(heapArr,op):
    if op==1:
        heapArr = prelocateUp(heapArr)
    else :
        heapArr = prelocateDown(heapArr)
    return heapArr

def insertHeap(heapArr,num):
    heapArr.append(num)
    heapArr = heapify(heapArr,1)
    return heapArr

def getMin(heapArr):
    ele = heapArr[0]
    heapArr[0] = heapArr[-1]
    heapArr.pop(-1)
    heapArr = heapify(heapArr,2)
    return ele,heapArr

a=[5,4,8,2,6]
heapArr = []
for i in xrange(0,len(a)):
    heapArr = insertHeap(heapArr,a[i])

#No 
sortedArr = []
for i in xrange(0,len(a)):
    [ele,heapArr] = getMin(heapArr)
    sortedArr.append(ele)
print sortedArr

回答by Jason

If you have push and pop, or are using built-in heapq lib, try documented solution:

如果您有 push 和 pop，或者正在使用内置 heapq lib，请尝试记录的解决方案：

from heapq import heappush, heappop
def heapsort(iterable):
    h = []
    for value in iterable:
        heappush(h, value)
    return [heappop(h) for i in range(len(h))]

heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]