這里寫目錄標題

堆的概念
堆的操作
- 向下調整
- 搞一個大堆
- 向上調整
- 入堆
- 出堆
使用Java中的堆
top-K問題
- 分享一個題目
堆排序

堆的概念

堆在邏輯上是一棵完全二叉樹
堆在物理上是儲存在陣列中的
進行堆操作時，可以將陣列寫作完全二叉樹，運用雙親的下標操作
雙親下標 parent
左孩子下標 = parent * 2 + 1；
右孩子下標 = parent * 2 + 2；
知道孩子下標（左孩子和右孩子都行）
parent = ( child - 1 ) / 2；
大根堆
任意節點的值都大于其孩子節點的值（左右孩子值的大小比較無要求）

堆的操作

向下調整

前提：左右子樹必須已經是一個堆

如某節點的左右子樹都是大堆，將這個樹向下調整成大堆

parent是開始節點的下標，child是其左孩子的下標
如果child超過或等于陣列長度，說明沒有左孩子，因為是完全二叉樹，也沒有右孩子，即說明這樹是大堆嘍
如果child<size，說明有左孩子
先判斷其有沒有右孩子，如果有并且大于左孩子，則child++，成為右孩子下標；如果沒有，child依舊是左孩子下標
判斷parent與child節點的大小，如果parent節點小于child節點，交換值，繼續向下調整，parent標記子孩子，child向下標記新的子孩子（因為子樹的節點變換了，不一定是大堆了，要繼續將其變為大堆）；如果parent節點大于child節點，直接break退出回圈，此時它就是一個大堆

    public void adjustDown(int[] array, int begin, int size) {
        int parent = begin;
        int child = parent * 2 + 1;
        while (child < size) {
            if (child + 1 < array.length && array[child + 1] > array[child]) {
                child++;
            }
            if (array[parent] < array[child]) {
                int temp = array[parent];
                array[parent] = array[child];
                array[child] = temp;
                parent = child;
                child = child*2+1;
            }else{
                break;
            }
        }
    }

搞一個大堆

堆就是一個陣列，創建欄位
找最后的一棵子樹，child為最后一個節點的下標，然后找到parent是父親節點的下標，進行向下調整，調整成大堆
對于每一棵子樹進行向下調整，直至最后一棵樹（parent=0，即parent標記第一個節點）

public class MyHeap {
    public int[] elem;
    public int useSize;
    public MyHeap() {
        this.elem = new int[10];
    }

    //建一個最大堆
    public void creatHeap(int[] array){
        for (int i = 0 ; i < array.length; i++) {
            this.elem[i] = array[i];
            this.useSize++;
        }
        //確定最后一棵子樹的父樹
        int child = this.useSize-1;
        int parent = (child-1)/2;
        //對于每棵子樹進行調換大小的操作
        for( ;parent>=0;parent--){
            adjustDown(parent,this.useSize);
        }
    }

    //向下調整
    public void adjustDown(int parent,int size){
        int child = parent*2+1;
        while(child < size) {
            if (child + 1 < len && this.elem[child + 1] > this.elem[child]) {
                child++;
            }
            if (this.elem[parent] < this.elem[child]) {
                int temp = this.elem[parent];
                this.elem[parent] = this.elem[child];
                this.elem[child] = temp;
                parent = child;
                child = parent * 2 + 1;
            } else {
                break;
            }
        }
    }

向上調整

前提：這個樹已經是一個堆
如某樹是一個大堆
向上調整用于 入堆或改變原來堆的葉子節點，再將其變為大堆
在這里插入圖片描述

向上調整的起點child，如果child<=0，說明完成調整了
比較孩子節點與父親節點的大小，如果孩子節點>父親節點，交換；否則，直接break退出回圈
交換節點后，新的父親節點為原parent的父親節點，新的孩子節點為原parent，進行回圈
由于原本就是一個大堆，只要孩子節點沒交換，一定小于父親節點，所以不用左右比較

    public void adjustUp(int[] arrays, int child){
        int parent = (child-1)/2;
        while(child > 0){
            if(arrays[parent] < arrays[child]){
                int temp = arrays[parent];
                arrays[parent] = arrays[child];
                arrays[child] = temp;
                child = parent;
                parent = (child-1)/2;
            }else{
                break;
            }
        }
    }

入堆

陣列尾插，不夠擴容，向上轉型

//this.elem已經是一個大堆啦
    public void adjustUp(int child){
        int parent = (child-1)/2;
        while(child > 0){
            if(this.elem[child] > this.elem[parent]){
                int temp = this.elem[child];
                this.elem[child] = this.elem[parent];
                this.elem[parent] = temp;
                child = parent;
                parent = (child-1)/2;
            }else{
                break;
            }
        }
    }

    public void push(int val){
        if(isFull()){
           this.elem = Arrays.copyOf(this.elem,2*this.elem.length);
        }
        this.elem[this.useSize] = val;
        this.useSize++;
        adjustUp(this.useSize-1);
    }

    public boolean isFull(){
        return this.useSize == this.elem.length;
    }

出堆

判斷堆是否為空
交換堆首元素與堆尾的元素，即交換陣列第一個元素和最后一個元素
堆的長度-1
向下調整

//this.elem是一個大堆
    public void pop(){
        if(isEmpty()){
            return;
        }
        int temp = this.elem[0];
        this.elem[0] = this.elem[this.useSize -1];
        this.elem[this.useSize -1] = temp;
        this.useSize--;
        adjustDown(0,this.useSize);
    }
    public boolean isEmpty(){
        return this.useSize == 0;
    }

在這里插入圖片描述

使用Java中的堆

默認是一個小堆

PriorityQueue<Integer> maxHeap = new PriorityQueue<>();

PriorityQueue的構造方法
在這里插入圖片描述

如果堆中的元素無法直接比較的話，可以用Java物件比較的兩種方法

建Comparator

class Student {
    private String name;
    private int age;

    public Student(String name, int age) {
        this.name = name;
        this.age = age;
    }
    public String getName() {
        return name;
    }
    public void setName(String name) {
        this.name = name;
    }
    public int getAge() {
        return age;
    }
    public void setAge(int age) {
        this.age = age;
    }

    @Override
    public String toString() {
        return "Student{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }
    
}
class AgeComparator implements Comparator<Student>{

    @Override
    public int compare(Student o1, Student o2) {
    //o1是前面的，o2是后面的
    //從小到大
        return o1.getAge()-o2.getAge();
    //從大到小
    //  return o2.getAge()-o1.getAge();
    }
}

    public static void main(String[] args) {
        //建最大堆
        PriorityQueue<Student> maxHeap = new PriorityQueue<>(new AgeComparator());
        maxHeap.offer(new Student("dong",18));
        maxHeap.offer(new Student("gang",20));
        maxHeap.offer(new Student("hui",16));
        System.out.println(maxHeap);
    }

    public static void main(String[] args) {
        PriorityQueue<Student> heap = new PriorityQueue<>(new Comparator<Student>() {
            @Override
            public int compare(Student o1, Student o2) {
                return o1.getAge()-o2.getAge();
            }
        });
    }

重寫Comparable的compareTo()方法

在這里插入圖片描述

class Student implements Comparable<Student>{
    private String name;
    private int age;

    public Student(String name, int age) {
        this.name = name;
        this.age = age;
    }
    public String getName() {
        return name;
    }
    public void setName(String name) {
        this.name = name;
    }
    public int getAge() {
        return age;
    }
    public void setAge(int age) {
        this.age = age;
    }

    @Override
    public String toString() {
        return "Student{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }

    @Override
    public int compareTo(Student o) {
    //建小堆
        return this.getAge()-o.getAge();
    //建大堆
        return o.getAge()-this.getAge();
    }
}
    public static void main(String[] args) {
        Student student1 = new Student("拉塞爾",29);
        Student student2 = new Student("亞歷山大",27);
        Student[] students = {student1,student2};
        Arrays.sort(students);
        System.out.println(Arrays.toString(students));

    }

在這里插入圖片描述

top-K問題

一組資料中找前k個最大（最小）的數

若找前k個最大的數，建立一個長度為k的最小堆
遍歷陣列，前k個元素建堆
堆建好后繼續遍歷陣列，如果元素比堆頂的元素大，出堆頂元素，如該元素，以此回圈
遍歷完成陣列，最后的堆中就是所求的元素

    public PriorityQueue<Integer> topK(int[] array,int k){
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(k, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2-o1;
            }
        });
        for (int i = 0; i < array.length; i++) {
            if(maxHeap.size() < k){
                maxHeap.offer(array[i]);
            }else{
                if(maxHeap.peek()>array[i]){
                    maxHeap.poll();
                    maxHeap.offer(array[i]);
                }
            }
        }
        return maxHeap;
    }

分享一個題目

https://leetcode-cn.com/problems/find-k-pairs-with-smallest-sums/
在這里插入圖片描述

    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k){
        PriorityQueue<List<Integer>> maxHeap = new PriorityQueue<>(k, new Comparator<List<Integer>>() {
            @Override
            public int compare(List<Integer> o1, List<Integer> o2) {
                return (o2.get(0)+o2.get(1)) - (o1.get(0)+o1.get(1));
            }
        });

        for (int i = 0; i < nums1.length; i++) {
            for (int j = 0; j < nums2.length; j++) {
                if(maxHeap.size() < k){
                    List<Integer> list = new LinkedList<>();
                    list.add(nums1[i]);
                    list.add(nums2[j]);
                    maxHeap.offer(list);
                }else{
                    List<Integer> list = maxHeap.peek();
                    int count = list.get(0) + list.get(1);
                    if(nums1[i] + nums2[j] < count){
                        List<Integer> list1 = new LinkedList<>();
                        list1.add(nums1[i]);
                        list1.add(nums2[j]);
                        maxHeap.poll();
                        maxHeap.offer(list1);
                    }
                }
            }
        }
        List<List<Integer>> list = new LinkedList<>();
        for (int i = 0; i < k && !maxHeap.isEmpty(); i++) {
            list.add(maxHeap.poll());
        }
        return list;
    }

此時堆頂元素就是這個陣列第第k小的元素

在這里插入圖片描述

堆排序

從小到大排列，此時this.elem是一個大堆了！！！

交換堆頂元素（第一個元素）和堆尾（最后一個元素），此時堆尾的元素就是此陣列中最大的元素
再對堆頂元素進行向下調整（注意范圍要-1，最后一個元素不參與此調整）
end–，再交換第一個元素和倒數第二個元素，此時倒數第二個元素就是第二大
依次回圈，直到end=0為止

    public void sort(){
        int end = this.useSize-1;
        while(end>0) {
            int temp = this.elem[0];
            this.elem[0] = this.elem[end];
            this.elem[end] = temp;
            adjustDown(this.elem, 0, end);
            end--;
        }
    }

認真生活，就能找到生活藏起來的糖果，
在這里插入圖片描述

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/303032.html

標籤：java

上一篇：詳解八大排序

下一篇：【Java】??認識例外、例外的基本使用、認識例外（例外詳解）??

人的一生會遇到三種人，一個驚艷了時光，一個溫柔了歲月，一個講懂了“堆”

這里寫目錄標題

堆的概念

堆的操作

向下調整

搞一個大堆

向上調整

入堆

出堆

使用Java中的堆

top-K問題

分享一個題目

堆排序