Куча Сортировка: как сортировать?

Я пытаюсь реализовать Heap Sort в Python, но я не могу понять, что это правильно. Я попытался реализовать этот псевдокод, но мой код не сортирует! Он просто просачивается к смехотворному эффекту. Я склонен думать, что проблема в этой строке:

замените корень (максимальное значение) кучи на последний элемент кучи

Как получить максимальное значение?

Это то, что у меня есть:

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)

И я нашел пример с почти той же проблемой:

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

Результаты разные, но оба смешны:

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

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

Ответы

Ответ 1

Я нашел его и почти понял, как это работает:

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)

Изменить

Эта реализация написана на основе моего собственного понимания алгоритма. Это длиннее, но для меня этот алгоритм гораздо яснее в этой реализации. Длительное именование - это помощь, когда вам нужно понять алгоритм, поэтому я оставил без изменений все длинные имена.

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()

Изменить

И оптимизированная версия:

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)

Ответ 2

Как получить максимальное значение? Вам не нужно "получать" его. Корень точно совпадает с максимальным, что определено свойство кучи.

Если вам сложно понять кучу сортировки, эта глава будет чрезвычайно полезна.

Я переписал ваш код:

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)

Он дает:

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

Ответ 3

Если у вас есть push и pop, или вы используете встроенную библиотеку heapq, попробуйте документированное решение:

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]

Ответ 4

Выбор сортировки является относительно прямым алгоритмом сортировки: пересечь массив, извлечь minun из первых n элементов, а затем извлечь min из следующих n-1 элементов...... Теперь это будет O (n ^ 2) алгоритм.

Поскольку вы всегда извлекаете мин, вы должны подумать об использовании минимальной кучи. он извлекает мин в O (log n) времени. извлечение min n раз приводит к O (n * log n) времени.

поэтому для сортировки кучи нужно просто построить кучу (heapify O (n)), а затем переместить массив и извлечь min n раз.

вы можете использовать python heap для создания кучи или создания собственного.

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

Ответ 5

Я нахожу, что различные реализации heapify, "сердце" кучи сортировки не ясны в интернете. Вот моя скромная попытка помочь сообществу, добавив простой, но ясный пример "heapify". Я использую векторы, чтобы избежать лишней путаницы манипуляции с массивами.

Этот метод генерирует 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 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

Ответ 6

Пример сортировки кучи с примером того, как изначально строить кучу

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