首页 > 编程语言 > 详细

最小的k个数1 堆排序实现

时间:2018-01-14 14:14:09      阅读:101      评论:0      收藏:0      [点我收藏+]

标签:叶子节点   gpo   新建   void   堆排序实现   oid   end   个数   时间   

// 使用堆排序实现 其时间复杂度为O(nlgn)
    private static void buildMaxHeap(int[] input, int end)
    {
        // 从非叶子节点开始进行
        for (int i = (end - 1) / 2; i >= 0; i--)
        {
            // 当前节点 cur的字节点位cur*2+1&cur*2+2
            int cur = i;
            // cur的右孩子存在
            while (cur * 2 + 1 < end)
            {
                int bigIndex = cur * 2 + 1;
                int rightOfCur = cur * 2 + 2;
                // 找出孩子节点中的最大值索引
                if (input[bigIndex] < input[rightOfCur])
                {
                    bigIndex++;
                }
                // input[cur]节点与input[bigIndex] 进行比较进
                if (input[cur] < input[bigIndex])
                {
                    int temp = input[cur];
                    input[cur] = input[bigIndex];
                    input[bigIndex] = temp;
                    // 尤其重要
                    cur = bigIndex;
                }
                else
                {
                    break;
                }

            }
        }
    }

    private static int[] minKOfNums(int[] nums, int k)
    {
        // 特殊值考虑
        if (nums == null || nums.length < k || k <= 0)
        {
            return null;
        }
        // 声明堆
        int[] maxHeap = new int[k];
        // 初始化
        for (int i = 0; i < k; i++)
        {
            maxHeap[i] = nums[i];
        }
        // 建成最大堆
        buildMaxHeap(maxHeap, maxHeap.length - 1);
        // 进行后续的比较
        for (int i = k; i < nums.length; i++)
        {
            if (maxHeap[0] > nums[i])
            {
                maxHeap[0] = nums[i];
                // 重新建maxHeap
                buildMaxHeap(maxHeap, maxHeap.length - 1);
            }
        }
        return maxHeap;
    }

最小的k个数1 堆排序实现

标签:叶子节点   gpo   新建   void   堆排序实现   oid   end   个数   时间   

原文:https://www.cnblogs.com/qingtianBKY/p/8283168.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号