首页 > 其他分享 >堆排

堆排

时间:2022-09-27 22:14:00浏览次数:30  
标签:index 堆排 nums int Heap adjustHeap 节点

堆排序

建堆,移动最值,维护堆
时间复杂度 初始化建堆O(n),排序重建堆O(nlog(n)) 总时间复杂度 O(nlog(n)); 不稳定
代码实现:最大堆最小堆的区别只是在节点和子节点比较

package leet;

import org.junit.Test;

import java.util.Arrays;

/**
 * @ClassName:Heap
 * @Description:TODO
 * @author:zgw
 * @date:2022/9/27 21:39
 */
public class Heap {
    @Test
    public void test() {
        int[] nums = new int[]{3, 3, 2, 1, 0};
        System.out.println(Arrays.toString(nums));
        Heap heap = new Heap();
        heap.heapSort(nums);
    }

    private void heapSort(int[] nums) {
        int n = nums.length;
        // 0-n的下标堆 第一个不为叶子节点的下标 n/2 -1,可验证
        for (int i = n / 2 - 1; i >= 0; i--) {
            adjustHeap(nums, i, n);
        }

        // 建堆完成后,index0是最大值,交换到最末尾,然后对index0继续维护
        for (int i = n - 1; i > 0; i--) {
            int t = nums[0];
            nums[0] = nums[i];
            nums[i] = t;
            adjustHeap(nums, 0, i);
        }
        System.out.println(Arrays.toString(nums));
    }

    private void adjustHeap(int[] nums, int index, int end) {
        // 下面的循环一直移动t值,直到t比左右子节点大
        int t = nums[index];
        for (int i = 2 * index + 1; i < end; i = i * 2 + 1) {
            // i=2*index+1为左子节点,i+1为右子节点 将i移动到左右子树中较大的一个
            if (i + 1 < end && nums[i + 1] > nums[i]) {
                i++;
            }
            if (nums[i] > t) {
                // 较大子节点比t大则交换,并把index指向原来子树的位置,继续循环
                nums[index] = nums[i];
                nums[i] = t;
                index = i;
            } else {
                break;
            }
        }
    }
}

标签:index,堆排,nums,int,Heap,adjustHeap,节点
From: https://www.cnblogs.com/beichuang/p/16736186.html

相关文章

  • 堆排序
    简介堆排序是利用堆这种数据结构而设计的一种排序算法,堆排序是一种选择排序,它的最坏,最好,平均时间复杂度均为O(nlogn),它也是不稳定排序。堆是具有以下性质的完全二叉树......
  • ac 838堆排序
    这里是维护一个m大小的堆,每一个比堆顶小的数字都放进来进行一次heapify。题目的意思我以为是只需要输出前m小的数字不需要排序,但是看答案意思需要,所以最后麻烦了一下#inc......
  • 堆排序
    voidHeapSort(intarr[],intstart,intend){ intdad=start; intson=dad*2+1; while(son<=end) { if(son+1<=end&&arr[son]<arr[son+1]) son++;......
  • 堆排序
    packagecom.lianzhu.filemanage.utils;importjava.util.Stack;/***栈排序*@description:栈的特性:先进后出如空数组【】*@step1:有一串数字4,8,7,9,2,6......
  • 堆排序 与 比较器
    堆排序假如给你一无序的数组,经过堆排序获得一组降序的数组1、首先我们将数组遍历,进行heapInsert,变为一个大根堆,建立堆的过程方法一:正序遍历+heapInsertO(N*logN)当需......
  • 经典排序之堆排序
    堆排序思路堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分......
  • 由浅入深!一文带你彻底明白堆排序
    本文中所有的代码全都是大根堆!实现语言是Java图片来源都是这位大神的,大神的文章也给了我很多启发数据结构之堆堆排序这个视频通俗易懂从什么是堆,什么是堆化,再到实现......
  • 十大排序算法之【堆排序】
    堆排序代码://头文件省略voidheapify(vector<int>&in,intbottom,inttop){intlargest=top;intlson=top*2+1;intrson=top*2+1;if(lson......
  • 快速排序和堆排序
    python快速排序、堆排序、计数排序、桶排序、基数排序_一只什么都不懂的码农的博客常用排序算法总结和对比_玖玖拾月陆的博客-CSDN博客_各种排序算法的总结和比较#快速......