`
hongjn
  • 浏览: 54972 次
  • 性别: Icon_minigender_1
  • 来自: 火星
社区版块
存档分类
最新评论

堆排序(HeapSort) Java实现

阅读更多
堆排序的思想是利用数据结构--。具体的实现细节:
1. 构建一个最大堆。对于给定的包含有n个元素的数组A[n],构建一个最大堆(最大堆的特性是,某个节点的值最多和其父节点的值一样大。这样,堆中的最大元素存放在根节点中;并且,在以某一个节点为根的子树中,各节点的值都不大于该子树根节点的值)。从最底下的子树开始,调整这个堆结构,使其满足最大堆的特性。当为了满足最大堆特性时,堆结构发生变化,此时递归调整对应的子树。
2. 堆排序算法,每次取出该最大堆的根节点(因为根节点是最大的),同时,取最末尾的叶子节点来作为根节点,从此根节点开始调整堆,使其满足最大堆的特性。
3. 重复上一步操作,直到堆的大小由n个元素降到2个。
4. gif 演示:http://upload.wikimedia.org/wikipedia/commons/4/4d/Heapsort-example.gif (来自wikipedia)



public class HeapSort {

    public static void sort(Comparable[] data) {
        // 构建最大堆
        buildMaxHeap(data);
        // 循环,每次把根节点和最后一个节点调换位置
        for (int i = data.length; i > 1; i--) {
            Comparable tmp = data[0];
            data[0] = data[i - 1];
            data[i - 1] = tmp;

            // 堆的长度减少1,排除置换到最后位置的根节点
            maxHeapify(data, 1, i - 1);
        }
    }

    // 根据输入数组构建一个最大堆
    private static void buildMaxHeap(Comparable[] data) {
        for (int i = data.length / 2; i > 0; i--) {
            maxHeapify(data, i, data.length);
        }
    }

    //堆调整,使其生成最大堆
    private static void maxHeapify(Comparable[] data, int parentNodeIndex, int heapSize) {
        // 左子节点索引
        int leftChildNodeIndex = parentNodeIndex * 2;
        // 右子节点索引
        int rightChildNodeIndex = parentNodeIndex * 2 + 1;
        // 最大节点索引
        int largestNodeIndex = parentNodeIndex;

        // 如果左子节点大于父节点,则将左子节点作为最大节点
        if (leftChildNodeIndex <= heapSize && data[leftChildNodeIndex - 1].compareTo(data[parentNodeIndex - 1]) > 0) {
            largestNodeIndex = leftChildNodeIndex;
        }

        // 如果右子节点比最大节点还大,那么最大节点应该是右子节点
        if (rightChildNodeIndex <= heapSize && data[rightChildNodeIndex - 1].compareTo(data[largestNodeIndex - 1]) > 0) {
            largestNodeIndex = rightChildNodeIndex;
        }

        // 最后,如果最大节点和父节点不一致,则交换他们的值
        if (largestNodeIndex != parentNodeIndex) {
            Comparable tmp = data[parentNodeIndex - 1];
            data[parentNodeIndex - 1] = data[largestNodeIndex - 1];
            data[largestNodeIndex - 1] = tmp;

            // 交换完父节点和子节点的值,对换了值的子节点检查是否符合最大堆的特性
            maxHeapify(data, largestNodeIndex, heapSize);
        }
    }

}
  • 大小: 644.6 KB
1
0
分享到:
评论
2 楼 LSQ6063 2012-02-14  
这个图显示的有待商确
1 楼 javaeye官理员 2011-12-14  

相关推荐

Global site tag (gtag.js) - Google Analytics