您现在的位置是:首页 > 正文

2024-02-01 05:51:26阅读 2
一.堆的定义

堆是计算机科学中一类特殊的数据结构的统称,堆通常可以被看做是一棵完全二叉树的数组对象。

二.API设计

在这里插入图片描述

三.代码实现

public class Heap<T extends Comparable<T>>{
    private T[] items;
    private int length;

    public Heap(int capacity) {
        this.length = 0;
        items = (T[])new Comparable[capacity + 1];
    }

    /**
     * 比较两个节点的大小
     * @param i
     * @param j
     * @return
     */
    private boolean less(int i,int j){
        return items[i].compareTo(items[j]) < 0;
    }

    private void swap(int i,int j){
        T temp = items[i];
        items[i] = items[j];
        items[j] = temp;
    }

    public void insert(T t){
        items[++length] = t;
        swim(length);
    }

    // 上浮算法
    private void swim(int k){
        while( k > 1){
            if (less(k/2,k)) swap(k,k/2);
            k /= 2;
        }
    }

    public T deleteMax(){
        T max = items[1];
        swap(1,length);
        items[length] = null;
        length--;
        sink(1);
        return max;
    }

    private void sink(int k){
        while(k*2 <= length){
            int max;
            if(k*2+1 <= length){
                if (less(k*2,k*2+1)) max = k*2+1;
                else max = k*2;
            }else{
                max = k*2;
            }
            if (less(k,max)) swap(k,max);
            else return;
        }
    }
}

四.堆排序

在这里插入图片描述

import java.util.Arrays;
import java.util.Random;

public class HeapSort {
    /**
     * 对source数组中的数据从小到大排列
     *
     * @param source
     */
    public static void sort(Comparable[] source) {
        Comparable[] heap = new Comparable[source.length + 1];
        createHeap(source, heap);
        int N = heap.length - 1;
        while (N != 1) {
            wrap(heap, 1, N);
            N--;
            sink(heap, 1, N);
        }
        System.arraycopy(heap, 1, source, 0, source.length);
    }

    private static void createHeap(Comparable[] source, Comparable[] heap) {
        System.arraycopy(source, 0, heap, 1, source.length);
        // 对堆中元素做下沉处理
        for (int i = (heap.length - 1) / 2; i > 0; i--) {
            sink(heap, i, heap.length - 1);
        }
    }

    /**
     * 判断heap堆中索引i处的元素是否小于索引j处的元素
     *
     * @param heap
     * @param i
     * @param j
     * @return
     */
    private static boolean less(Comparable[] heap, int i, int j) {
        return heap[i].compareTo(heap[j]) < 0;
    }

    /**
     * 交换heap堆中i索引和j索引处的值
     *
     * @param heap
     * @param i
     * @param j
     */
    private static void wrap(Comparable[] heap, int i, int j) {
        Comparable temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }

    /**
     * 在heap堆中,对target处元素做下沉,范围是0~range
     *
     * @param heap
     * @param target
     * @param range
     */
    private static void sink(Comparable[] heap, int target, int range) {
        while (2 * target <= range) {
            int max;
            if (2 * target + 1 <= range) {
                if (less(heap, 2 * target, 2 * target + 1)) max = 2 * target + 1;
                else max = 2 * target;
            } else {
                max = 2 * target;
            }
            if (less(heap, target, max)) wrap(heap, max, target);
            target = max;
        }
    }

    public static Integer[] randomArray(int N) {
        Random random = new Random();
        Integer[] array = new Integer[N];
        for(int i = 0;i < N;i++){
            array[i] = random.nextInt(100);
        }
        return array;
    }

    public static void main(String[] args) {
        Integer[] array = randomArray(10);
        sort(array);
        System.out.println(Arrays.toString(array));
    }
}

在这里插入图片描述

网站文章

  • 你的网卡真有千兆么?——千兆网卡传输速度解析 热门推荐

    随着PS3it技术的破解和可以利用电脑FTP向PS3传送文件,千兆网卡成为了不少玩家必备的工具。要知道PS3it技术本身自带千兆网卡,如果利用FTP软件以及电脑上的千兆网卡进行文件传输,其速度远比采用...

    2024-02-01 05:51:19
  • JavaScript Equality Table

    JavaScript Equality Table

    Tables displaying the issue: and == Moral of the story use ===

    2024-02-01 05:51:13
  • Autoware pure_pursuit节点适配差速底盘

    Autoware pure_pursuit节点适配差速底盘

    Autoware pure_pursuit节点输出的话题是 "/twist_raw", 需要转换为我们小车底盘控制速度的话题,我这里直接用"/cmd_vel"。主要任务是消息格式的转换,下面详细介绍。...

    2024-02-01 05:50:44
  • 调用API

    3.编写API请求:编写代码向API发送请求,包括所需参数和API密钥等。使用最常见的请求方法是HTTP请求,包括GET、POST、PUT、DELETE等。4.解析API响应:API会返回响应数据,需...

    2024-02-01 05:50:30
  • Codeforces 1221E. Game With String

    传送门首先每一段连续的 $...$ 都是互不影响的,所以可以一段段考虑考虑最简单的情况,此时每一段都大于等于 $a$ 并且小于 $2b$ ,那么每一段都只能放一次,胜负直接根据段数即可得到答案考虑如果存在段长小于 $a$ 却大于等于 $b$ 的情况,此时后手可以随时放在那个位置,当然也可以不放,这样胜负就被掌握在后手手里(他可以随时选择交换先后手)所以对于上面那一种情况,...

    2024-02-01 05:50:23
  • spring boot 整合sharding jdbc 遇到的一些问题以及实例源码

    spring boot 整合sharding jdbc 遇到的一些问题以及实例源码

    文章目录一、整合1.pom.xml 新增依赖(这里默认你项目中已经有了Mysql的依赖)2.配置3.遇到的问题“The bean 'dataSource', defined in class path...

    2024-02-01 05:49:55
  • mysqld_safe Directory &#39;/var/lib/mysql&#39; for UNIX socket file don&#39;t exists

    原因:mysql找不着socket文件。 解决办法: 1、修改mysql配置文件my.cnf中[mysqld]下的socket配置项。效果如下。 [mysqld] socket = /tmp/mysql.sock 2、终极解决办法:重启服务器。 ...

    2024-02-01 05:49:47
  • 洛谷 P1618

    https://www.luogu.org/problemnew/show/P1618 题目描述 将1,2,…,9共9个数分成三组,分别组成三个三位数,且使这三个三位数的比例是A:B:C,试求出所有满足条件的三个三位数,若无解,输出“No!!!”。 //感谢黄小U饮品完善题意 输入输出格式 输入格式: 三个数,A B C。 输出格式: 若干行,每行3个数字。按照每...

    2024-02-01 05:49:41
  • 设计模式之责任链模式

    设计模式之责任链模式

    不同级别的权限检查由不同的权限处理者来执行,如果某个处理者无法处理权限请求,则请求将被传递给下一个处理者。让我们想象一个问题解决系统,根据问题的复杂程度,系统中的不同专家级别的工程师会负责处理不同级别...

    2024-02-01 05:49:13
  • 浅谈MIL、SIL、PIL、HIL

    浅谈MIL、SIL、PIL、HIL

    MBD开过过程中,经常会接触到MIL、SIL、PIL、HIL,下文将从定义着手,将他们区别开来。 定义: MIL:Model in loop, 验证控制算法模型是否满足功能需求 SIL: Software in loop, 在PC上验证模型是否与代码功能一致 PIL:Processor in loop, 在目标处理器上验证模型是否与代码功能一致 HIL:Hardw

    2024-02-01 05:49:07