Heap 排序 - 改良的選擇排序

December 8, 2021

選擇排序的概念簡單，以降冪為例，每次從未排序部份選最小值，插入已排序部份的後端，時間主要花費於在整個未排序部份尋找最小值，如果能讓搜尋最小值的方式加快，選擇排序法的速率也就可以加快。

Heap 排序會先建立堆積樹（Heap tree），父子節點間的值具有順序關係，可以加快值的搜尋，可算是改良的選擇排序法。

解法思路

堆積樹是個二元樹，父節點最多有兩個子節點，父節點若小於子節點，稱為最小堆積（Min heap），父節點若大於子節點，稱為最大堆積（Max heap），同一層的節點不考慮大小關係，例如是個最小堆積樹：

Heap 排序 - 改良的選擇排序

若使用陣列來儲存堆積樹的元素，為了計算方便，使用的起始索引是 1 而不是 0，索引 1 是樹根位置，如果左子節點儲存在陣列中的索引為 s，則其父節點的索引為 s / 2，而右子節點為 s + 1，就如上圖所示，將上圖的堆積樹轉換為陣列後如下：

Heap 排序 - 改良的選擇排序

若要建立堆積樹，以最小堆積為例，加至堆積樹的元素會先放置在最後一個節點位置，然後檢查父節點是否小於子節點，將小的元素不斷與父節點交換，直到滿足堆積樹的條件為止，例如在上圖的堆積加入一個元素 12，則堆積樹的調整方式如下所示：

Heap 排序 - 改良的選擇排序

建立好最小堆積樹後，樹根一定是最小值，將最小值取出，然後調整樹為最小堆積樹，不斷重複這兩個步驟，就可以達到排序的效果。

最小值取出方式是將樹根與最後一個節點交換，然後切下最後一個節點；調整堆積樹的方式，是找出父節點兩子節點中較小的一個進行交換，如下所示：

Heap 排序 - 改良的選擇排序

調整完畢後，樹根節點又是最小值了，於是可以重覆這個步驟，再取出最小值，並調整樹為堆積樹，如下所示：

Heap 排序 - 改良的選擇排序

由於使用陣列來儲存堆積樹，每次將最後一個節點與樹根交換的動作，就是將最小值放至後端的陣列，最後陣列就會變為已排序的狀態。

程式實作

#include <stdio.h> 
#include <stdlib.h> 
#define LEN 10
#define OFFSET 1
#define SWAP(x,y) {int t; t = x; x = y; y = t;} 

void heapSort(int*, int len, int(*)(int, int));
void heapTree(int*, int, int(*)(int, int)); 
void selectFromHeap(int*, int, int(*)(int, int)); 

void bubbleLeaf(int*, int, int(*)(int, int));
int isBubbleable(int*, int, int, int(*)(int, int));

void bubbleRoot(int*, int, int(*)(int, int));
int idxFromChilds(int*, int, int, int(*)(int, int));
int isRightLeafSuitable(int*, int, int, int(*)(int, int));

void print(int*, int len);
int ascending(int, int);
int descending(int, int);

int main(void) { 
    int num[LEN] = {10, 9, 1, 2, 5, 3, 8, 7, 12, 11};

    heapSort(num, LEN, descending); 
    print(num, LEN);
    
    heapSort(num, LEN, ascending); 
    print(num, LEN);
    
    system("PAUSE");

    return 0; 
}

void heapSort(int* num, int len, int(*compar)(int, int)) {
    heapTree(num, len, compar);
    selectFromHeap(num, len, compar); 
}

void heapTree(int* num, int len, int(*compar)(int, int)) { 
    int i, end;
    for(i = 1, end = len + 1; i < end; i++) { bubbleLeaf(num, i, compar); }
}

void selectFromHeap(int* num, int len, int(*comp)(int, int)) {
    int end;
    for(end = len; end > OFFSET; end--) {
        SWAP(num[1 - OFFSET], num[end - OFFSET]);
        bubbleRoot(num, end, comp);
    }
}

void bubbleLeaf(int* num, int eleIdx, int(*compar)(int, int)) {
    int childIdx, parentIdx;
    for(childIdx = eleIdx, parentIdx = eleIdx / 2;
        isBubbleable(num, childIdx, parentIdx, compar);
        childIdx = parentIdx, parentIdx = childIdx / 2) {
         SWAP(num[parentIdx - OFFSET], num[childIdx - OFFSET]); 
    }
}

int isBubbleable(int* num, int childIdx, 
                 int parentIdx, int(*compar)(int, int)) {
    return childIdx > OFFSET && 
           compar(num[parentIdx - OFFSET], num[childIdx - OFFSET]) < 0;
}

void bubbleRoot(int* num, int end, int(*comp)(int, int)) {
    int parentIdx, childIdx;
    for(parentIdx = 0 + OFFSET, 
        childIdx = idxFromChilds(num, parentIdx, end, comp);
        childIdx < end && 
        comp(num[childIdx - OFFSET], num[parentIdx - OFFSET]) > 0; 
        parentIdx = childIdx, 
        childIdx = idxFromChilds(num, parentIdx, end, comp)) {
        SWAP(num[parentIdx - OFFSET], num[childIdx - OFFSET]); 
    }    
}

int idxFromChilds(int* num, int parentIdx, int end, int(*comp)(int, int)) {
   int childIdx = parentIdx * 2;
   return isRightLeafSuitable(num, childIdx, end, comp) ? 
              childIdx + 1 : childIdx;
}

int isRightLeafSuitable(int* num, int childIdx, 
                        int end, int(*comp)(int, int)) {
    return childIdx < end - 1 && 
           comp(num[childIdx + 1 - OFFSET], num[childIdx - OFFSET]) > 0;
}

void print(int* arr, int len) {
    int i;
    for(i = 0; i < len; i++) { printf("%d ", arr[i]); } 
    printf("\n");
}

int ascending(int a, int b) { return a - b; }
int descending(int a, int b) { return -ascending(a, b); }

import java.util.*;
import static java.lang.System.out;
import static java.util.Collections.swap;

public class Sort {
    public static <T extends Comparable<? super T>> 
        int ascending(T t1, T t2) {  return t1.compareTo(t2); }

    public static <T extends Comparable<? super T>> 
        int descending(T t1, T t2) { return -ascending(t1, t2); }
    
    public static <T extends Comparable<? super T>> 
        void heapSort(List<T> list) { heapSort(list, Sort::ascending); }
        
    private static final int OFFSET = 1;
        
    public static <T> void heapSort(
        List<T> list, Comparator<? super T> c) {
        heapTree(list, c);
        selectFromHeap(list, c);
    }
    
    private static <T> void heapTree(List<T> list, Comparator<? super T> c) {
        for(int i = 1, end = list.size() + 1; i < end; i++) { 
            bubbleLeaf(list, i, c); 
        }
    }
    
    private static <T> void selectFromHeap(List<T> list, 
                                Comparator<? super T> c) {
        for(int end = list.size(); end > OFFSET; end--) {
            swap(list, 1 - OFFSET, end - OFFSET);
            bubbleRoot(list, end, c);
        }
    }
    
    private static <T> void bubbleLeaf(List<T> list, 
                                int eleIdx, Comparator<? super T> c) {
        for(int childIdx = eleIdx, parentIdx = eleIdx / 2;
            isBubbleable(list, childIdx, parentIdx, c);
            childIdx = parentIdx, parentIdx = childIdx / 2) {
             swap(list, parentIdx - OFFSET, childIdx - OFFSET); 
        }
    }
    
    private static <T> boolean isBubbleable(List<T> list, int childIdx, 
                 int parentIdx, Comparator<? super T> c) {
        return childIdx > OFFSET && c.compare(
           list.get(parentIdx - OFFSET), list.get(childIdx - OFFSET)) < 0;
    }
    
    private static <T> void bubbleRoot(List<T> list, 
                                int end, Comparator<? super T> c) {
        for(int parentIdx = 0 + OFFSET, 
                childIdx = idxFromChilds(list, parentIdx, end, c);
            childIdx < end && 
            c.compare(list.get(childIdx - OFFSET), 
                      list.get(parentIdx - OFFSET)) > 0; 
            parentIdx = childIdx, 
            childIdx = idxFromChilds(list, parentIdx, end, c)) {
            swap(list, parentIdx - OFFSET, childIdx - OFFSET); 
        }
    }

    private static <T> int idxFromChilds(List<T> list, 
                         int parentIdx, int end, Comparator<? super T> c) {
        int childIdx = parentIdx * 2;

        return isRightLeafSuitable(list, childIdx, end, c) ? 
              childIdx + 1 : childIdx;
    }

    private static <T> boolean isRightLeafSuitable(List<T> list, 
                          int childIdx, int end, Comparator<? super T> c) {
        return childIdx < end - 1 && 
               c.compare(list.get(childIdx + 1 - OFFSET), 
                         list.get(childIdx - OFFSET)) > 0;
    }

    public static void main(String[] args) {
        List<Integer> list = 
            new ArrayList<>(Arrays.asList(10, 9, 1, 2, 5, 3, 8, 7, 12, 11));
        
        heapSort(list);
        out.println(list);
        
        heapSort(list, Sort::descending);
        out.println(list);
    }
}

def ascending(a, b): return a - b
def descending(a, b): return -ascending(a, b)

__OFFSET = 1
    
def heapSort(xs, comp = ascending):
    if not xs:
        return []
    else:
        heapped = heapTree([], xs, comp)
        return selectFromHeap(heapped, [], comp)

def heapTree(heapped, xs, comp):
    if not xs:
        return heapped
    else:
        return heapTree(bubbleLeaf(heapped, xs[0], comp), xs[1:], comp)

def bubbleLeaf(heapped, child, comp):
    if not heapped:
        return [child]
    else:
        parentIdx = (len(heapped) + 1) // 2
        if comp(heapped[parentIdx - __OFFSET], child) < 0:
            heappedChilds = (heapped[parentIdx - __OFFSET + 1:] + 
                             [heapped[parentIdx - __OFFSET]])
            heappedParents = heapped[0:parentIdx - __OFFSET]
            return bubbleLeaf(heappedParents, child, comp) + heappedChilds
        else:
            return heapped + [child]
        
def selectFromHeap(heapped, sorted, comp):
    if len(heapped) == 1:
        return heapped + sorted
    else:
        rootSorted = [heapped[0]] + sorted
        unheapped = [heapped[-1]] + heapped[1:-1]
        leftHeapped = bubbleRoot(unheapped, 1, 0, comp)
        return selectFromHeap(leftHeapped, rootSorted, comp)
        
def bubbleRoot(unheapped, parentIdx, heappedLen, comp):
    childLIdx = (parentIdx * 2) - heappedLen
    if len(unheapped) == 1 or childLIdx > len(unheapped):
        return unheapped
    else:
        childIdx = idxFromChilds(childLIdx, unheapped, comp)
        if comp(unheapped[childIdx - __OFFSET], unheapped[0]) > 0:
            heapped = ([unheapped[childIdx - __OFFSET]] + 
                        unheapped[1:childIdx - __OFFSET])
            rightUnheapped = ([unheapped[0]] + 
                               unheapped[childIdx + 1 - __OFFSET:])
            return heapped + bubbleRoot(rightUnheapped, 
                                        heappedLen + childIdx, 
                                        heappedLen + childIdx - 1, comp)
        else:
            return unheapped

def idxFromChilds(childLIdx, unheapped, comp):
    return (childLIdx + 1 if childLIdx < len(unheapped) and 
                             comp(unheapped[childLIdx + 1 - __OFFSET], 
                                  unheapped[childLIdx - __OFFSET]) > 0 
                          else childLIdx)

list = [10, 9, 1, 2, 5, 3, 8, 7, 12, 11]

print(heapSort(list))
print(heapSort(list, descending))

object Sort {
    private val OFFSET = 1
    
    def heap[T](xs: List[T], compare: (T, T) => Boolean):List[T] = {
        if(xs.isEmpty) Nil
        else {
            val heapped = heapTree(Nil, xs, compare)
            selectFromHeap(heapped, Nil, compare)
        }
    }
    
    private def heapTree[T](heapped: List[T], xs: List[T],
                   compare: (T, T) => Boolean): List[T] = {
        if(xs.isEmpty) heapped
        else {
            heapTree(bubbleLeaf(heapped, xs(0), compare), xs.tail, compare)
        }
    }
            
    private def bubbleLeaf[T](heapped: List[T], child: T,
                   compare: (T, T) => Boolean): List[T] = {
        if(heapped.isEmpty) List(child)
        else {
            val parentIdx = (heapped.size + 1) / 2
            if(compare(child, heapped(parentIdx - OFFSET))) {
                val heappedChilds = 
                      heapped.slice(parentIdx - OFFSET + 1, heapped.size) 
                      ++ List(heapped(parentIdx - OFFSET))
                val heappedParents = heapped.slice(0, parentIdx - OFFSET)
                bubbleLeaf(heappedParents, child, compare) ++ heappedChilds
            }
            else heapped ++ List(child)
        }
    }
    
    private def selectFromHeap[T](heapped: List[T], sorted: List[T], 
                   compare: (T, T) => Boolean): List[T] = {
        if(heapped.size == 1) heapped ++ sorted
        else {
            val rootSorted = heapped.head :: sorted
            val unheapped = heapped.last :: 
                            heapped.slice(1, heapped.size - 1)
            val leftHeapped = bubbleRoot(unheapped, 1, 0, compare)
            selectFromHeap(leftHeapped, rootSorted, compare)
        }
    }
    
    private def bubbleRoot[T](unheapped: List[T], parentIdx: Int, 
                   heappedLen: Int, compare: (T, T) => Boolean): List[T] = {
        val childLIdx = (parentIdx * 2) - heappedLen
        if(unheapped.size == 1 || childLIdx > unheapped.size) unheapped
        else {
            val childIdx = idxFromChilds(childLIdx, unheapped, compare)
            if(compare(unheapped(childIdx - OFFSET), unheapped.head)) {
                val heapped = unheapped(childIdx - OFFSET) :: 
                              unheapped.slice(1, childIdx - OFFSET)
                val rightUnheapped = unheapped.head :: 
                      unheapped.slice(childIdx + 1 - OFFSET, unheapped.size)
                heapped ++ bubbleRoot(rightUnheapped, heappedLen + childIdx, 
                                      heappedLen + childIdx - 1, compare)
            }
            else unheapped
        }
    }
    
    private def idxFromChilds[T](childLIdx: Int, 
                    unheapped: List[T], compare: (T, T) => Boolean) = {
        if(childLIdx < unheapped.size &&
           compare(unheapped(childLIdx + 1 - OFFSET), 
                   unheapped(childLIdx - OFFSET))) {
             childLIdx + 1
        } 
        else childLIdx
    }
}

val list = List(10, 9, 1, 2, 5, 3, 8, 7, 12, 11)

println(Sort.heap[Int](list, _ > _))
println(Sort.heap[Int](list, _ < _))

class Sort
    @@ascending = ->(a, b) { a - b }
    @@descending = ->(a, b) { -@@ascending.call(a, b) }
    
    def self.ascending; @@ascending end
    def self.descending; @@descending end
    
    OFFSET = 1
    
    def self.heap(xs, comp)
        if xs.empty?
            []
        else
            heapped = heapTree([], xs, comp)
            selectFromHeap(heapped, [], comp)
        end
    end
    
    def self.heapTree(heapped, xs, comp)
        if xs.empty?
            heapped
        else
            heapTree(bubbleLeaf(heapped, xs[0], comp), xs[1..-1], comp)
        end
    end
    private_class_method :heapTree

    def self.bubbleLeaf(heapped, child, comp)
        if heapped.empty?
            [child]
        else
            parentIdx = (heapped.size + 1) / 2
            if comp.call(heapped[parentIdx - OFFSET], child) < 0
                heappedChilds = (heapped[parentIdx - OFFSET + 1..-1] + 
                                 [heapped[parentIdx - OFFSET]])
                heappedParents = heapped[0...parentIdx - OFFSET]
                bubbleLeaf(heappedParents, child, comp) + heappedChilds
            else
                heapped + [child]
            end
        end
    end
    private_class_method :bubbleLeaf    
            
    def self.selectFromHeap(heapped, sorted, comp)
        if heapped.size == 1
            heapped + sorted
        else
            rootSorted = [heapped[0]] + sorted
            unheapped = [heapped.last] + heapped[1...-1]
            leftHeapped = bubbleRoot(unheapped, 1, 0, comp)
            selectFromHeap(leftHeapped, rootSorted, comp)
        end
    end
    private_class_method :selectFromHeap
    
    def self.bubbleRoot(unheapped, parentIdx, heappedLen, comp)
        childLIdx = (parentIdx * 2) - heappedLen
        if unheapped.size == 1 or childLIdx > unheapped.size
            unheapped
        else
            childIdx = idxFromChilds(childLIdx, unheapped, comp)
            if comp.call(unheapped[childIdx - OFFSET], unheapped[0]) > 0
                heapped = ([unheapped[childIdx - OFFSET]] + 
                            unheapped[1...childIdx - OFFSET])
                rightUnheapped = ([unheapped[0]] + 
                                   unheapped[childIdx + 1 - OFFSET..-1])
                heapped + bubbleRoot(rightUnheapped, 
                                       heappedLen + childIdx, 
                                       heappedLen + childIdx - 1, comp)
            else
                unheapped
            end
        end
    end
    private_class_method :bubbleRoot
    
    def self.idxFromChilds(childLIdx, unheapped, comp)
        (childLIdx < unheapped.size and 
         comp.call(unheapped[childLIdx + 1 - OFFSET], 
                   unheapped[childLIdx - OFFSET]) > 0) ? 
         childLIdx + 1 : childLIdx
    end
    private_class_method :idxFromChilds
end

list = [10, 9, 1, 2, 5, 3, 8, 7, 12, 11]

print(Sort.heap(list, Sort.ascending).to_s + "\n")
print(Sort.heap(list, Sort.descending).to_s + "\n")

function ascending(a, b) {return a - b;}
function descending(a, b) {return -ascending(a, b);}

var heapSort = function() {
    function swap(list, i, j) {
        var ele = list[i];
        list[i] = list[j];
        list[j] = ele;
    }

    var OFFSET = 1;
   
    function sort(list, c) {
        heapTree(list, c);
        selectFromHeap(list, c);
    }
    
    function heapTree(list, c) {
        for(var i = 1, end = list.length + 1; i < end; i++) { 
            bubbleLeaf(list, i, c); 
        }
    }
    
    function selectFromHeap(list, c) {
        for(var end = list.length; end > OFFSET; end--) {
            swap(list, 1 - OFFSET, end - OFFSET);
            bubbleRoot(list, end, c);
        }
    }
    
    function bubbleLeaf(list, eleIdx, c) {
        for(var childIdx = eleIdx, parentIdx = parseInt(eleIdx / 2);
            isBubbleable(list, childIdx, parentIdx, c);
            childIdx = parentIdx, parentIdx = parseInt(childIdx / 2)) {
             swap(list, parentIdx - OFFSET, childIdx - OFFSET); 
        }
    }
    
    function isBubbleable(list, childIdx, parentIdx, c) {
        return childIdx > OFFSET && c(
           list[parentIdx - OFFSET], list[childIdx - OFFSET]) < 0;
    }
    
    function bubbleRoot(list, end, c) {
        for(var parentIdx = 0 + OFFSET, 
                childIdx = idxFromChilds(list, parentIdx, end, c);
            childIdx < end && 
            c(list[childIdx - OFFSET], list[parentIdx - OFFSET]) > 0; 
            parentIdx = childIdx, 
            childIdx = idxFromChilds(list, parentIdx, end, c)) {
            swap(list, parentIdx - OFFSET, childIdx - OFFSET); 
        }
    }

    function idxFromChilds(list, parentIdx, end, c) {
        var childIdx = parentIdx * 2;
        return isRightLeafSuitable(list, childIdx, end, c) ? 
              childIdx + 1 : childIdx;
    }

    function isRightLeafSuitable(list, childIdx, end, c) {
        return childIdx < end - 1 && 
               c(list[childIdx + 1 - OFFSET], list[childIdx - OFFSET]) > 0;
    }
    
    return sort;
}();

var list = [10, 9, 1, 2, 5, 3, 8, 7, 12, 11];

heapSort(list, ascending);
print(list);

heapSort(list, descending);
print(list);

ascending a b = a - b
descending a b = -ascending a b

slice from to xs = take (to - from) (drop from xs)
tailFrom from xs = slice from (length xs) xs
initUntil until xs = slice 0 until xs

offset = 1

heapSort xs comp =
    if xs == [] then []
    else
        let heapped = heapTree [] xs comp
        in selectFromHeap heapped [] comp

heapTree heapped xs comp =
    if xs == [] 
        then heapped
        else heapTree (bubbleLeaf heapped (head xs) comp) (tail xs) comp

bubbleLeaf heapped child comp =
    if heapped == [] then [child]
    else
        let parentIdx = (length heapped + 1) `div` 2
        in
            if (comp (heapped !! (parentIdx - offset)) child) < 0 then
                let heappedChilds = 
                        (tailFrom (parentIdx - offset + 1) heapped) ++ 
                            [heapped !! (parentIdx - offset)]
                    heappedParents = initUntil (parentIdx - offset) heapped
                in (bubbleLeaf heappedParents child comp) ++ heappedChilds
            else
                heapped ++ [child]
                
selectFromHeap heapped sorted comp =
    if (length heapped == 1) then heapped ++ sorted
    else
        let rootSorted = (head heapped) : sorted
            unheapped = (last heapped) : (init $ tail heapped)
            leftHeapped = bubbleRoot unheapped 1 0 comp
        in selectFromHeap leftHeapped rootSorted comp
        
bubbleRoot unheapped parentIdx heappedLen comp =
    if (length unheapped == 1) || (childLIdx > length unheapped) 
    then unheapped
    else
        let childIdx = idxFromChilds childLIdx unheapped comp
        in
            if comp (unheapped !! (childIdx - offset)) (head unheapped) > 0
            then
                let heapped = (unheapped !! (childIdx - offset)) :
                              (slice 1 (childIdx - offset) unheapped)
                    rightUnheapped = 
                        (head unheapped) : 
                        (tailFrom (childIdx + 1 - offset) unheapped)
                in heapped ++ 
                    (bubbleRoot rightUnheapped (heappedLen + childIdx) 
                    (heappedLen + childIdx - 1) comp)
            else unheapped
    where childLIdx = (parentIdx * 2) - heappedLen
            
idxFromChilds childLIdx unheapped comp =
    if childLIdx < (length unheapped) && 
       (comp (unheapped !! (childLIdx + 1 - offset)) 
             (unheapped !! (childLIdx - offset))) > 0
        then childLIdx + 1
        else childLIdx
        
main = sequence [print $ heapSort list ascending, 
                 print $ heapSort list descending]
    where list = [10, 9, 1, 2, 5, 3, 8, 7, 12, 11]

分享到 LinkedIn 分享到 Facebook 分享到 Twitter