文章目錄
- 一、堆
- 1.堆的概念
- 二、堆的基本操作
- 1.創建堆與向下調整
- 2.創建堆的時間復雜度
- 3.向上調整
- 4.模擬優先級佇列的offer操作
- 5.模擬優先級佇列的poll操作
- 三、優先級佇列集合的使用
- 1.優先級佇列中的比較規則
- 2.特殊的比較方式
- 3.刨析PriorityQueue中的offer原始碼
- 四、有關堆的面試題
- 1.堆排序（從小到大排）
- 2.topK問題
- 3.查找和最小的K對數字
認識堆前的基本概念：
1、完全二叉樹：若二叉樹的深度為h，則除第h層外，其他層的結點全部達到最大值，且第h層的所有結點都集中在左子樹，2、滿二叉樹：滿二叉樹是一種特殊的的完全二叉樹，所有層的結點都是最大值，
3、已知樹的其中一個孩子結點下標為i，則它的父親結點的下標為(i-1)/2
4、已知樹的其中一個父親結點下標為i，則它的孩子結點的下標為i*2+1
一、堆
1.堆的概念
- 堆邏輯上是一棵完全二叉樹
- 堆物理上是保存在陣列中
- 滿足任意結點的值都大于其子樹中結點的值，叫做大堆，或者大根堆，或者最大堆；反之，則是小堆，或者小根堆，或者最小堆，當一個堆為大堆時，它的每一棵子樹都是大堆，
- 堆的基本作用是，快速找集合中的最值
二、堆的基本操作
1.創建堆與向下調整
創建堆只有兩種堆可以創建，要不就是大根堆，要不就是小根堆，而要滿足大根堆還是小根堆的邏輯，要向下調整的操作才能實作，
要想自己實作堆，堆本身就是一個陣列，因此創建一個陣列來創建堆，（此處以創建大根堆為例）
創建堆思路：首先i從最后一個父親結點開始，向下調整為大根堆，當調整完其中每一個堆時，將父親結點的值移到孩子結點的值，而孩子結點的值設定為2*parent+1，當然，如果孩子結點的值一旦大于整個堆的結點數，則在i-1的結點處去調整堆，每一個子樹都是按照相同的情況去調整為大堆，
注意的是，算出一個孩子結點可能是其中一個二叉子樹的左節點，當然它也有可能有右節點，因此首先判斷它有沒有右節點，即child+1<len，并且如果有右節點的話要比較右節點和它的值哪一個大，如果右節點比左節點的值大，則child直接指向右節點，否則不需要調整child，再比較兩個孩子結點的陣列是否比它們的父親結點的值大，
當parent的下標指向有以它為根節點深度為3的樹時，如果兩個孩子結點比較后數值較大的孩子結點與父親結點比較，若父親結點的數值更大，則不用繼續調整了，
例如：
說明：此處的usedSize為陣列的最大下標，
public void creatHeap(int[] array) {
for (int i = 0; i < array.length; i++) {
elem[i]=array[i];
usedSize++;
}
for (int i = (array.length-1-1)/2; i >=0 ; i--) {
adjustDown(i,usedSize);
}
}
//每次調整后的結束位置：usedSize
/*
向下調整
*/
public void adjustDown(int parent,int len) {
int child = parent*2+1;
while(child<len) {
if(child+1<len&&elem[child]<elem[child+1]) {
child++;
}
if(elem[child]>elem[parent]) {
int tmp = elem[parent];
elem[parent]=elem[child];
elem[child]=tmp;
parent=child;
child=2*parent+1;
}else {
break;
}
}
}
2.創建堆的時間復雜度
有不少初學者認為，創建堆的程序為O(N*log2^N)，N為結點個數，其實不然，創建堆的時間復雜度實際上為O(N)，證明程序如下：
說明：h為整棵樹的深度，
因為向下調整是從最后一個父親結點開始的，因此每一層的結點數乘以它所要調整的堆的高度，還是以上圖為例，**下標為0的結點除了它所在的層以外其余的層數都要調整為大根堆，這一層調整的時間復雜度就為2的0次方乘以(h-1)；下標為1和2的結點除了它所在的層和比他低的層外都要調整為大根堆，這一層調整的時間復雜度就為2的1次方乘以(h-2)，**以此類推，最后的時間復雜度為：
式子1：
但我們要對此進行化簡，采用數學上的錯位相減法，令等式的兩邊同乘以2，得：
式子2：
讓式子2減去式子1：
轉化為：
由等比數列的求和公式：
得：
又因為假設該堆有n個結點，深度為h，因為結點數n=2的h次方-1 ，因此高度為h=log2為底的（n+1），將h代入T(n)中得：
因此，創建堆的時間復雜度為T(n)=O(N)，
3.向上調整
向上調整一般適用于優先級佇列（已經確定是大堆還是小堆后）中的入隊操作后調整堆為大堆還是小堆，
還是以下圖為例：我們向上調整是先從最后一個結點的下標作為孩子結點來進行調整，已知孩子結點的下標則能求出父親結點的下標，若孩子結點的下標小于0，則直接退出回圈，當其中一個孩子結點的值小于父親結點的值，則直接退出回圈，（因為已經確定了原本的整個堆為大堆）是因為能夠直接確定整個堆已經是一個大堆，
//向上調整
public void adjustUp(int child) {
int parent = (child-1)/2;
while(child>0) {
if(elem[child]>elem[parent]) {
int tmp = elem[parent];
elem[parent]=elem[child];
elem[child]=elem[parent];
child=parent;
parent=(child-1)/2;
}else {
break;
}
}
}
4.模擬優先級佇列的offer操作
優先級佇列的offer操作，是從堆的最后一個位置處插入元素，并且插入后要進行向上調整來確保堆是大堆，
//向上調整
public void adjustUp(int child) {
int parent = (child-1)/2;
while(child>0) {
if(elem[child]>elem[parent]) {
int tmp = elem[parent];
elem[parent]=elem[child];
elem[child]=elem[parent];
child=parent;
parent=(child-1)/2;
}else {
break;
}
}
}
public void offer(int val) {
if(isFull()) {
elem = Arrays.copyOf(elem,2*elem.length);
}
elem[usedSize++]=val;
adjustUp(usedSize-1);
}
public boolean isFull() {
return usedSize==elem.length;
}
5.模擬優先級佇列的poll操作
優先級佇列中的poll操作是使堆的堆頂元素出隊（前提該堆已經是一個大堆），那么我們可以讓堆頂元素與堆的最后一個位置的元素交換，交換后再根據向下調整來調整堆為一個大堆，
代碼：
//出最大的元素
public void pop() {
if(isEmpty()) {
return;
}
int tmp = elem[0];
elem[0]=elem[usedSize-1];
elem[usedSize-1]=tmp;
usedSize--;
adjustDown(0,usedSize);
}
public boolean isEmpty() {
return usedSize==0;
}
三、優先級佇列集合的使用
1.優先級佇列中的比較規則
Student類：
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 +
'}';
}
}
Test類：
public static void main(String[] args) {
PriorityQueue<Student> queue = new PriorityQueue<>();
queue.offer(new Student("bit",18));
queue.offer(new Student("zjr",8));
System.out.println(queue);
}
若直接入隊，則編譯器會報錯，
并且我們在學習Compartor比較器時，對一個型別的陣列排序要用Comparable介面或者Comparator介面，不能直接進行比較，
public static void main(String[] args) {
Student[] students = new Student[2];
students[0] = new Student("zjr",12);
students[1] = new Student("bit",89);
Arrays.sort(students,new NameComparator());
System.out.println(Arrays.toString(students));
}
原因是PriorityQueue不知道我們是按照哪個屬性去排的序，我們點入PriorityQueue的原始碼當中，看到了它的其中一個構造方法中能有一個Comparator比較器，
**當然我們也可以用Comparable比較器，但是對類的嵌入性太強，**若重寫的compareTo方法只是比較的是它的年齡，則該類只能按照年齡去比較，而不能用姓名去比較了，此處就直接省略了，
那Comparator可以直接創建多個類來實作該介面，可用作多個不同型別的屬性的比較，如：
class AgeComparator implements Comparator<Student> {
@Override
public int compare(Student o1, Student o2) {
return o1.getAge()-o2.getAge();
}
}
class NameComparator implements Comparator<Student> {
@Override
public int compare(Student o1, Student o2) {
return o1.getName().compareTo(o2.getName());
}
}
public static void main(String[] args) {
PriorityQueue<Student> priorityQueue = new PriorityQueue<>(new AgeComparator());
priorityQueue.offer(new Student("bit",18));
priorityQueue.offer(new Student("zjr",8));
System.out.println(priorityQueue);
}
2.特殊的比較方式
若兩個參考進行比較，是地址不同的兩個參考，若在該參考的類中重寫equals和hashCode方法，并且創建物件的時候創建的屬性都是相同的，則呼叫equals回傳的是true，
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 +
'}';
}
@Override
public boolean equals(Object o) {
//是不是兩個參考 同時指向一個物件
if (this == o) return true;
//如果傳進來是一個null
if (o == null) return false;
Student student = (Student) o;
//
return age == student.age &&
Objects.equals(name, student.name);
}
//hashmap講完后
@Override
public int hashCode() {
return Objects.hash(name, age);
}
}
public static void main(String[] args) {
Student student1 = new Student("bit",1);
Student student2 = new Student("bit",1);
System.out.println(student1 == student2);//列印結果false
System.out.println(student1.equals(student2));//列印結果true
}
3.刨析PriorityQueue中的offer原始碼
offer中的原始碼：
我們可以看到，如果不是第一次入隊，則要采用向上調整的方式入隊，
點入siftUp方法當中，可以看到它會判定使用哪一個比較器，
實際上它們方法內部的操作都是一樣的，只不過Comparator根據一些屬性的排序的范圍更廣，引數x為即將要入隊的元素，k為隊尾的下標，e為父親結點的元素此時呼叫compare方法，o1則為即將要插入的元素，o2為父親結點元素，若compare方法內部回傳的是o1-o2，則創建的是小堆，相反，若compare方法內部回傳的是o2-o1，則創建的是大堆，
四、有關堆的面試題
1.堆排序（從小到大排）
面試題1：問若一個陣列用堆排序要按照從小到大排序，需要如何排序？
答：一個陣列根據從小到大排序，要創建大堆來排；一個陣列根據從大到小排序，要創建小堆來排，
此處就以創建大堆為例，首先將堆頂的元素和堆中的最后一個元素交換，交換后再向下調整，調整后再與堆的倒數第二個元素進行交換，
代碼：
public void HeapSort() {
int end = usedSize-1;
while(end>0) {
int tmp = elem[0];
elem[0]=elem[end];
elem[end]=tmp;
adjustDown(0,end);
end--;
}
}
2.topK問題
面試題2：問如何從100w個數字中取得最小的10數字，列印出來的數字不用排序，
答：若要從N個數字中取得最小的K個數字，則需要創建大小為K的大堆來獲取，若壓迫從N個數字中取得最大的K個數字，則需要創建大小為K的小堆來獲取，
此處以大堆為例，若創建堆的時候里面的元素小于K，則入隊，用i來遍歷100個數字，若其中有一個數字比堆頂元素小，則于與堆頂元素交換，
此處以10個數字取最小的3個數，
代碼：
public static void 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 {
int top = maxHeap.peek();
if(top > array[i]) {
maxHeap.poll();
maxHeap.offer(array[i]);
}
}
}
System.out.println(maxHeap);
}
public static void main(String[] args) {
int[] array = {1, 31, 2, 10, 7, 35, 21, 19, 56,45};//找到前3個最小的資料
topk(array, 3);
}
//列印結果： [7, 1, 2]
3.查找和最小的K對數字
對應leetcode題
思路：此題涉及到topK問題，但是與上面的topK問題又有些不同，因為要找和最小的K對數字，因此要創建大堆來找，整個方法的回傳型別為List<List<Integer>>，則我們可以將每對數字看作一個List<Integer>型別，并且創建一個PriorityQueue只放入List<Integer>型別的資料，跟topK一樣，如果其中有top > nums1[i]+nums2[j]，則top出隊而nums1[i]與nums2[j]變為List<Integer>型別入隊，最后佇列中只剩下k對最小的數字，將它們存入到List<List<Integer>>型別中回傳即可，
class Solution {
public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
PriorityQueue<List<Integer>> queue = new PriorityQueue<>(k, new Comparator<List<Integer>>(){
public int compare(List<Integer> o1,List<Integer> o2) {
return (o2.get(0) + o2.get(1)) - (o1.get(0) + o1.get(1));
}
});
//取最小值是為了防止兩個陣列一個比較少的時候【1】 【1,2,3】
//并且nums1和nums2均為升序排列
for(int i = 0; i < Math.min(nums1.length, k); i++){
for(int j = 0; j < Math.min(nums2.length, k); j++){
if(queue.size() < k) {
List<Integer> pair = new ArrayList<>();
pair.add(nums1[i]);
pair.add(nums2[j]);
queue.add(pair);
}else {
int top = queue.peek().get(0) + queue.peek().get(1);
//大于K就出佇列
if(top > nums1[i]+nums2[j]){
List<Integer> pair = new ArrayList<>();
queue.poll();
pair.add(nums1[i]);
pair.add(nums2[j]);
queue.add(pair);
}
}
}
}
List<List<Integer>> res = new LinkedList<>();
for(int i =0; i < k && !queue.isEmpty(); i++){
res.add(queue.poll());
}
return res;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/413511.html
標籤：其他