美文网首页
堆排序及其时间复杂度分析

堆排序及其时间复杂度分析

作者: nafoahnaw | 来源:发表于2018-12-02 22:25 被阅读0次
    public class HeapUtil {
    
        /**
         * Heap数据结构是由列表或者数组抽象而来
         * 这个数据结构可以看作是一个不完整的二叉树
         * 规定列表的第一个元素为二叉树的根结点
         * 并且假设 parentIndex = i,则leftChildIndex = 2*i,rightChildIndex = 2*i + 1
         * 1<=index<=array.legnth + 1
         *
         * 最大堆的定义是对于array[parentIndex] >= array[leftChildIndex] && array[parentIndex] >= array[rightChildIndex]
         * 最小堆则相反
         * T(N) = O(logN)
         * @param array
         * @param index
         */
        public static void maxHeapify(int[] array, int index, int startIndex, int endIndex){
            int leftChildIndex = (index + 1) * 2;
            int rightChildIndex = leftChildIndex + 1;
    
            if(leftChildIndex > endIndex + 1) {
                //说明是叶子结点
                return ;
            }
    
            int turnWhere = 0;
    
            int maxValOfChildren = rightChildIndex > endIndex + 1 ? array[leftChildIndex - 1]
                    : Math.max(array[leftChildIndex - 1], array[rightChildIndex - 1]);
    
            if(array[index] >= maxValOfChildren){
                //没必要交换
                return;
            }else{
                //0:根节点和左边互换
                //1:根节点和右边互换
                if(rightChildIndex <= endIndex + 1 && maxValOfChildren == array[rightChildIndex - 1]){
                    turnWhere = 1;
                    int temp = array[index];
                    array[index] = array[rightChildIndex - 1];
                    array[rightChildIndex - 1] = temp;
                }else{
                    int temp = array[index];
                    array[index] = array[leftChildIndex - 1];
                    array[leftChildIndex - 1] = temp;
                }
    
            }
    
            if(turnWhere == 0){
                maxHeapify(array, leftChildIndex - 1, startIndex, endIndex);
            }else{
                maxHeapify(array, rightChildIndex - 1, startIndex, endIndex);
            }
        }
    
        /**
         * 将一个数组转换成一个最大堆
         * T(N) = O(N)
         * 这个时间复杂度不能简单的看作O(NlogN)
         * 对于长度为N的数组,(我们不考虑不完整二叉树的情况),有N/2个叶子节点
         * 对于叶子节点的父节点来说maxHeapify实际上只需要做一次交换即可
         * 同理对于叶子节点的父节点的父节点来说maxHeapify实际上只需要做2次交换
         * 所以对于一个深度为L的二叉树,做一次maxHeapify实际包含的O(1)操作为L次
         * 那么对于N/4(叶子结点总数为N/2则其父节点个数为N/4)个深度为1的父节点运行的时间为N/4 * C(C表示常数时间)
         * 对于N/8个深度为2的父节点运行的时间为N/8 * 2 * C
         * .
         * .
         * .
         * 对于根结点来说,只有一个并且深度为lgN运行时间为1 * lgN * C
         * 则T(N) = N/4 * 1 * C + N/8 * 2 * C + N/16 * 3 * C + ... + 1 * lgN * C
         * 为了更好的表示我们假设N/4=2^k
         * 则buildMaxHeapFromArray的运行时间可以表示为
         * C * 2^k * (1/2^0 + 2/2^1 + 3/2^2 + ... + (k+1)/2^k)
         * (1/2^0 + 2/2^1 + 3/2^2 + ... + (k+1)/2^k)是一个有上界的常数
         * 则T(N) = C * N/4 = O(N)
         */
        public static void buildMaxHeapFromArray(int[] array, int startIndex, int endIndex){
            //问题1:为什么从n/2开始
            //因为对于任何长度为n的数组A,A[n/2 + 1......n]都是叶子节点
            //所以n/2是最后一个非叶子节点,以该节点为根结点的局部二叉树的深度=1
            for (int i = (endIndex - startIndex + 1) / 2; i >= startIndex; i--) {
                maxHeapify(array, i, startIndex, endIndex);
            }
        }
    
        /**
         * 通过最大堆使得输入的无序数组array排序
         * @param array
         * @return
         */
        public static int[] heapSort(int[] array){
            int[] sortedArray = new int[array.length];
    
            for (int i = 0; i < sortedArray.length; i++) {
                //step1.构造最大堆
                buildMaxHeapFromArray(array, 0, array.length - i - 1);
                sortedArray[i] = array[0];
                array[0] = array[array.length - i - 1];
            }
    
            for (int i = 0; i < array.length; i++) {
                System.out.print(sortedArray[i] + ",");
            }
    
            return null;
        }
    
        public static void main(String args[]) {
            heapSort(new int[] {21, 14, 10, 15, 33, 2, 3, 16, 4, 1});
        }
    
    
    }
    
    public class Node {
    
        public Node(int val, Node leftChild, Node rightChild){
            this.val = val;
            this.leftChild = leftChild;
            this.rightChild = rightChild;
        }
    
        private int val;
    
    
        private Node leftChild;
    
    
        private Node rightChild;
    
        /**
         * Getter method for property leftChild.
         *
         * @return property value of leftChild
         */
        public Node getLeftChild() {
            return leftChild;
        }
    
        /**
         * Setter method for property leftChild.
         *
         * @param leftChild value to be assigned to property leftChild
         */
        public void setLeftChild(Node leftChild) {
            this.leftChild = leftChild;
        }
    
        /**
         * Getter method for property rightChild.
         *
         * @return property value of rightChild
         */
        public Node getRightChild() {
            return rightChild;
        }
    
        /**
         * Setter method for property rightChild.
         *
         * @param rightChild value to be assigned to property rightChild
         */
        public void setRightChild(Node rightChild) {
            this.rightChild = rightChild;
        }
    
        /**
         * Getter method for property val.
         *
         * @return property value of val
         */
        public int getVal() {
            return val;
        }
    
        /**
         * Setter method for property val.
         *
         * @param val value to be assigned to property val
         */
        public void setVal(int val) {
            this.val = val;
        }
    }
    
    

    相关文章

      网友评论

          本文标题:堆排序及其时间复杂度分析

          本文链接:https://www.haomeiwen.com/subject/rvgscqtx.html