堆排序

堆排序(Heapsort) 是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法. 堆是一個(gè)近似完全二叉樹的結(jié)構(gòu), 并同時(shí)滿足堆的性質(zhì): 即子節(jié)點(diǎn)的鍵值或索引總是大/小于它的父節(jié)點(diǎn)

若堆是什么樣的結(jié)構(gòu)不清楚的, 可以點(diǎn)這里

堆節(jié)點(diǎn)的訪問

通常堆是通過數(shù)組來實(shí)現(xiàn)的, i是堆中的一個(gè)節(jié)點(diǎn)的下標(biāo), 則:

父節(jié)點(diǎn)下標(biāo): (i -1) >>> 1;
左子節(jié)點(diǎn)的下標(biāo): 2*i + 1;
右子節(jié)點(diǎn)的下標(biāo): 2*1 + 2;

堆排序的策略

1. 從最后一個(gè) parent節(jié)點(diǎn)開始, 塑造最大堆(就是將parent, left, right 中的最大值放置到 parent位置), 一直到堆頂, 經(jīng)過這一步, 整個(gè)堆中的最大值就位于index=0的位置
2. 將第一步中的最大值(index=0)與數(shù)組的末尾節(jié)點(diǎn)兌換(注意這時(shí) index=2 和 index=3都是下面子堆的最大值), 再在剩余部分構(gòu)建最大值, 然后再重復(fù)將最大值與剩余數(shù)組中最后節(jié)點(diǎn)更換值, 再次構(gòu)建最大堆, 直到最后一個(gè)元素.

廢話不說了, 直接上代碼:

import java.util.Arrays;

/**
 * Created by xjk on 1/12/17.
 */
public class HeapSort {

    private static int[] sort = new int[]{1, 0, 10, 20, 3, 5, 6, 4, 9, 8, 12, 17, 34, 11};

    public static void main(String[] args) {
        buildMaxHeapify(sort);
        heapSort(sort);
        System.out.println(Arrays.toString(sort));
    }

    /**
     * 創(chuàng)建最大樹
     * @param data
     */
    private static void buildMaxHeapify(int[] data){
        // 獲取數(shù)組的最后一個(gè)父節(jié)點(diǎn)的index
        int startIndex = getParentIndex(data.length - 1);
        // 從最后一個(gè)父節(jié)點(diǎn)開始排序
        // 每次調(diào)用 maxHeapify 其實(shí)是將一顆二叉樹中最大的值放到parent位置, 而這里是從底層往上
        // 從而最終效果是, 整個(gè)數(shù)組中的每棵樹的最大值都在parent位置
        for(int i = startIndex; i >= 0; i--){
            maxHeapify(data, data.length, i);
        }
    }

    private static void heapSort(int[] data){
        // 1. 將最大樹的頭節(jié)點(diǎn)(即整棵樹的最大值)與末尾節(jié)點(diǎn)交換
        // 2. 排除最大值, 數(shù)組的剩余部分進(jìn)行最大值排序
        // 3. 重復(fù) 1, 2 步驟, 直達(dá)最頂?shù)哪莻€(gè)節(jié)點(diǎn)
        for(int i = data.length - 1; i > 0; i--){
            int temp = data[0];
            data[0] = data[i];
            data[i] = temp;
            maxHeapify(data, i, 0);
        }
    }

    /**
     * 創(chuàng)建最大堆
     * @param data
     * @param heapSize 需要?jiǎng)?chuàng)建最大堆的大小, 一般在sort時(shí)候會(huì)用到
     * @param index 當(dāng)前需要?jiǎng)?chuàng)建最大堆的位置
     */
    private static void maxHeapify(int[] data, int heapSize, int index){
        // 當(dāng)前點(diǎn)與左右子節(jié)點(diǎn)的比較
        int left = getLeftChildIndex(index);
        int right = getRightChildIndex(index);

        int largest = index;
        if(left < heapSize && data[index] < data[left]){
            largest = left;
        }
        if(right < heapSize && data[largest] < data[right]){
            largest = right;
        }

        // 獲取子節(jié)點(diǎn)中的最大值后可能需要交換, 交換后最大的值就在父節(jié)點(diǎn)
        if(largest != index){
            int temp = data[index];
            data[index] = data[largest];
            data[largest] = temp;
            maxHeapify(data, heapSize, largest);
        }
    }

    /**
     * 獲取父節(jié)點(diǎn)
     * @param current
     * @return
     */
    private static int getParentIndex(int current){
        return (current - 1) >>> 1;
    }

    /**
     * 獲取左子節(jié)點(diǎn)的
     * @param current
     * @return
     */
    private static int getLeftChildIndex(int current){
        return (current << 1) + 1;
    }

    /**
     * 獲取右子節(jié)點(diǎn)的坐標(biāo)
     * @param current
     * @return
     */
    private static int getRightChildIndex(int current){
        return (current << 1) + 2;
    }

}

總結(jié)

整堆排序過程其實(shí)就三步:

1. 構(gòu)建最大堆(buildMaxHeapify)
2. 將頭節(jié)點(diǎn)與為節(jié)點(diǎn)更換, 更換后將除尾節(jié)點(diǎn)外的數(shù)組看作一個(gè)堆, 對(duì)這個(gè)堆進(jìn)行最大值排序(heapSort)
3. 重復(fù)第二步, 直達(dá)最后一個(gè)節(jié)點(diǎn) (heapSort)

參考資料:
HeapSort
vickyqi 堆排序