堆排序(java实现)

一、前言

堆是一个数组,它可以看成近似的完全二叉树。表示堆的数组包括两个属性:A.length数组元素的个数,A.heapSize表示多少个元素存在数组中。这里的关系是:

 0<= A.heapSize<=A.length

树的根节点为A[1],堆排序的时间复杂度为O(nlgn)。二叉堆分为两种形式:最大堆和最小堆。最大堆是父节点>=子节点。最小堆即相反。下面用java实现最大堆,主要参考算法导论。

二、最大堆实现

由于数组没有heapSize,因此这里自己需要自己处理一下。

public class HeapSort {

    public static void main(String[] args) {
        HeapSort hs = new HeapSort();
        // 此处的-1不作为堆中的元素,只是让数组从1开始计数
        int a[] = { -1, 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 };
        int heapSize = a.length - 1;
        hs.build_max_heap(a);
        hs.heapSort(a);
        hs.heapExtractMax(a, heapSize);
        hs.print(a);
    }

    /**
     * 取出最大值
     */
    public int heapMaximum(int[] a) {
        return a[1];
    }

    /**
     * 取出最大元素的值,并从数组中取出
     */
    public int heapExtractMax(int a[], int heapSize) {
        if (heapSize < 1) {
            throw new RuntimeException("heap underflow");
        }
        int max = a[1];
        a[1] = a[heapSize];
        heapSize = heapSize - 1;
        max_heapify(a, 1, heapSize);
        return max;
    }

    /**
     * 增加某个结点的值
     */
    public void heapIncreaseKey(int[] a, int i, int key) {
        if (key < a[i]) {
            throw new RuntimeException("new key is smaller than current key");
        }
        a[i] = key;
        while (i > 1 && a[parent(i)] < a[i]) {
            swap(a, i, parent(i));
            i = parent(i);
        }

    }

    /**
     * 插入元素
     */
    public void maxHeapInsert(int[] a, int key, int heapSize) {
        heapSize = heapSize + 1;
        a[heapSize] = 0;
        heapIncreaseKey(a, heapSize, key);
    }

    /**
     * 堆排序
     */
    public void heapSort(int a[]) {
        build_max_heap(a);
        int len = a.length - 1;
        for (int i = len; i >= 2; i--) {
            swap(a, 1, i);
            len = len - 1;
            max_heapify(a, 1, len);
        }

        print(a);
    }

    /**
     * 建立最大堆
     */
    public void build_max_heap(int[] a) {
        int i = a.length / 2;
        int heap_size = a.length - 1;
        for (; i >= 1; i--) {
            max_heapify(a, i, heap_size);
        }
    }

    /**
     * 对于树高度为h来说,时间复杂度为O(h)
     */
    public void max_heapify(int[] a, int i, int heap_size) {
        int l = left(i);
        int r = right(i);
        int largest;
        if (l <= heap_size && a[l] > a[i]) {
            largest = l;
        } else {
            largest = i;
        }

        if (r <= heap_size && a[r] > a[largest]) {
            largest = r;
        }
        if (largest != i) {
            swap(a, largest, i);
            max_heapify(a, largest, heap_size);
        }
    }
    /**
     *  父结点
     */
    public int parent(int i) {
        return i / 2;
    }
    /**
     *  左孩子
     */
    public int left(int i) {
        return 2 * i;
    }
    /**
     *  右孩子
     */
    public int right(int i) {
        return 2 * i + 1;
    }
    /**
     *  交换数组中两个元素的值
     */
    public void swap(int a[], int x, int y) {
        try {
            int t = a[x];
            a[x] = a[y];
            a[y] = t;
        } catch (Exception e) {
            e.printStackTrace();
            System.out.println("x:" + x + ";y:" + y);
        }
    }

    /**
     * 打印
     */
    public void print(int[] a) {
        for (int i : a) {
            System.out.println("a=>" + i);
        }
    }

}

三、总结

堆排序总体上还是很简单的,算法导论上已经写的很是清楚明白了。这本书大三时候买的,当时没怎么看,现在重新看,经典终究是经典啊,希望坚持看完。内功加强中ing~~~~~

参考:算法导论

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • MIT公开课没有讲到的内容,堆排序主要部分内容引用自Blog:https://www.cnblogs.com/An...
    Alex90阅读 1,337评论 0 0
  • 堆排序 堆排序基本简介 1991年的计算机先驱奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德(Robert ...
    BlackMammba阅读 1,871评论 0 10
  • 基础概念#### 堆排序是比较基础的排序算法,也是我认为比较难的一种算法,因为它的流程比较多,理解起来不会像冒泡排...
    一只小哈阅读 28,352评论 9 32
  • 版本记录 前言 将数据结构和算法比作计算机的基石毫不为过,追求程序的高效是每一个软件工程师的梦想。下面就是我对算法...
    刀客传奇阅读 1,269评论 0 0
  • 今天在好朋友的推荐下,看了这部电影,里面有几个情节的非常有感触! 1.那个小白人,从用“血袋子”作战到和血袋子作战...
    火然开朗阅读 533评论 2 1