目錄
一、堆的定義及本質(zhì)
二、堆的核心操作
1、向下調(diào)整
2、堆的創(chuàng)建
3、向上調(diào)整
?三、堆的比較器傳入及堆中簡單函數(shù)的實現(xiàn)
四、堆的應用
1、用于OS調(diào)度進程
2、topk問題
?3、堆排序
一、堆的定義及本質(zhì)
堆在Java中是以優(yōu)先級隊列來表現(xiàn)的（PrityQueue），不傳入外部比較器則以小堆來實現(xiàn)（取出最小值）
前提：優(yōu)先級隊列中的元素具備比較能力（1.元素類型本身是可以比較的 2.通過構(gòu)造方法傳入一個外部比較器）
堆的作用：常用來在頻繁變動的數(shù)據(jù)集中找出最值
堆的本質(zhì)：邏輯上是完全二叉樹，本質(zhì)上是數(shù)組
堆的定義：
堆總是滿足下列性質(zhì)：
1.堆中某個節(jié)點的值總是不大于或不小于其父節(jié)點的值；
2、堆總是一棵完全二叉樹。
將根節(jié)點最大的堆叫做最大堆或大根堆，根節(jié)點最小的堆叫做最小堆或小根堆。常見的堆有二叉堆、斐波那契堆等。堆是非線性數(shù)據(jù)結(jié)構(gòu)，相當于一維數(shù)組，有兩個直接后繼。
?對于一個結(jié)點 2*index+1 是他的左節(jié)點 2*index+2是右節(jié)點? ?（index-1）/ 2 可以求得父節(jié)點
二、堆的核心操作
1、向下調(diào)整
當我們從堆頂取走一個最值時，這時堆的結(jié)構(gòu)已經(jīng)發(fā)生變化，我們往往用堆的最后一個結(jié)點來代替堆的根，但此時有可能這個值已經(jīng)不滿足堆的定義，我們需要對其進行向下調(diào)整，此時只有堆根部不滿足堆的定義
?我們此時對根部進行調(diào)整
我們首先想到在根的左右結(jié)點中找到最小的值來判斷是否大于根，如果根已經(jīng)是最小值，則滿足堆的定義，不需要進行交換，否則根與最小值進行交換
//對堆的根部進行向下調(diào)整
//結(jié)束調(diào)整的條件？ 已經(jīng)滿足堆的結(jié)構(gòu)，無需調(diào)整 當前結(jié)點已經(jīng)是葉子結(jié)點，下邊沒有節(jié)點，無需調(diào)整
public void justDown(int arr[],int size,int index){
int left=2*index+1;//判斷左子樹是否存在，如果沒有左子樹，必沒有右子樹（完全二叉樹性質(zhì)）
while (left<size){
int min=left+1<size&&arr[left+1]<arr[left]?left+1:left;//找出左右子樹中的最小值
int largest=arr[index]<=arr[min]?index:min;//在根和最小值中再找出最小值
if (largest==index) break;//如果根就是最小值 堆結(jié)構(gòu)已滿足 退出循環(huán)
swap(arr,index,min); //不滿足交換根和最小值，根等于最小值進行下一次調(diào)整
index=min;
left=index*2+1;
}
}
private void swap(int[] arr, int index, int min) {
int temp=arr[index];
arr[index]=arr[min];
arr[min]=temp;
}2、堆的創(chuàng)建
在我們已經(jīng)掌握向下調(diào)整的情況下，如何將一個完全二叉樹調(diào)整為堆呢？
我們可以對每個結(jié)點進行向下調(diào)整，使每個結(jié)點都滿足堆的定義
但我們知道向下調(diào)整的結(jié)束條件是當前結(jié)點已經(jīng)滿足堆的結(jié)構(gòu)或者當前結(jié)點是葉子結(jié)點，因此我們沒有必要對葉子結(jié)點進行調(diào)整，而在完全二叉樹中我們很容易找到最后一個結(jié)點（size-1）是最后一個結(jié)點的下標 而他的父節(jié)點是（size-1-1）/ 2? ?那么自他的父節(jié)點之后就全是葉子節(jié)點
public void creatHeap(int[] arr,int size){
for (int i=(size-2)/2;i>=0;i--){
justDown(arr,size,i);
}
}為什么從上到下不行？因為我們向下調(diào)整是由要求的，必須左右子樹已經(jīng)是一個堆結(jié)構(gòu)了 如果不理解可以畫圖。。
?
在經(jīng)歷一次向下調(diào)整時我們發(fā)現(xiàn)最小的1永遠沒有走到頂部的機會，為什么呢，因為我們沒有滿足向下調(diào)整的定義。沒有找到真正最小的那個數(shù)調(diào)整到堆頂?
3、向上調(diào)整
在我們創(chuàng)建完成一個堆的時候，往往需要往堆里邊添加新的元素，由于我們從數(shù)組【0，size）是已經(jīng)創(chuàng)建好的堆結(jié)構(gòu)，在我們新添加一個元素時，往往需要向上調(diào)整
public void justUp(int[] arr,int index){
int parent=(index-1)/2;//父節(jié)點下標
while (arr[index]>arr[parent]){//當子節(jié)點大于父節(jié)點時我們需要向上調(diào)整
swap(arr,index,parent);
index=parent;//新的Index是他的父節(jié)點
parent=(index-1)/2;//新的parent結(jié)點
}
}?三、堆的比較器傳入及堆中簡單函數(shù)的實現(xiàn)
假設當前有一個person類，里邊的屬性有姓名和年齡，此時person是默認不支持比較的
public class person{
String name;
int age;
}在不修改person類的情況下我們?nèi)绾螌崿F(xiàn)比較年齡呢？
答案是采用外部比較器
static class PersonComparator implements Comparator<Person>{
@Override
public int compare(Person o1, Person o2) {
return o1.age-o2.age;
}
} static class PersonComparator implements Comparator<Person>{
@Override
public int compare(Person o1, Person o2) {
return o1.age-o2.age;
}
}
public static void main(String[] args) {
PriorityQueue<Person> pq=new PriorityQueue(new PersonComparator());
pq.add(new Person("小明",11));
pq.add(new Person("小紅花",9));
pq.add(new Person("小剛",21));
while (!pq.isEmpty()){
System.out.println(pq.poll().toString());
}
}
堆的簡單函數(shù)全實現(xiàn)：
public class MyPriorityQueue{
long arr[];
int size;
public MyPriorityQueue(){//由于我們的元素類型是long類型沒有采用泛型，所以不涉及傳入比較器
arr=new long[20];
size=0;
}
public void add(long val){//往堆中加入一個元素
ensureCapacity();//保證數(shù)組空間夠用
arr[size]=val;
justUp(arr,size);//新加入的元素需要向上調(diào)整維持一個堆結(jié)構(gòu)
size++;
}
public long peek(){//查看堆頂部元素
if (size<0){
throw new RuntimeException("隊列是空的");
}
return arr[0];
}
public long poll(){//彈出堆頂部的元素
if (size<0){
throw new RuntimeException("隊列是空的");
}
long res=arr[0];//先記錄需要返回的元素
arr[0]=arr[size-1];//把最后一個元素調(diào)整到堆的頂部并向下調(diào)整
arr[size-1]=0;//最后一個元素交換到堆頂，那么它就要改為默認值
size--;
justDown(arr,size,0);
return res;
}
public int size(){
return size;
}
private void justDown(long[] arr, int size, int index) {
int left=index*2+1;
while (left<size){//如果還有子節(jié)點（不是葉子節(jié)點）
int min=left+1<size&&arr[left+1]<arr[left]?left+1:left;//找到左右子結(jié)點中的最小值
int largest=arr[min]<arr[index]?min:index;//找到最小的值
if (largest==index) break;//如果index本身就是最小值說明他已經(jīng)滿足堆結(jié)構(gòu)不需要調(diào)整
swap(arr,min,index);//交換index和最小值
index=min;//新的index
left=index*2+1;//新的最小值
}
}
public void check(){//檢查是否滿足堆結(jié)構(gòu)
if (size<0||size>arr.length){
throw new RuntimeException("size越界");
}
for (int i=0;i<size;i++){
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left >= size) {
// 說明是葉子，跳過
continue;
}
// 左孩子破壞了規(guī)則
if (arr[i] > arr[left]) {
throw new RuntimeException(String.format("[%d] 位置的值大于其左孩子的值了", i));
}
// 右孩子破壞了規(guī)則
if (right < size && arr[i] > arr[right]) {
throw new RuntimeException(String.format("[%d] 位置的值大于其右孩子的值了", i));
}
}
}
private void justUp(long[] arr, int index) {
while (index!=0){
int parent=(index-1)/2;
if (arr[parent]<=arr[index]) return;
swap(arr,index,parent);
index=parent;
}
}
public boolean isEmpty(){
return size==0;
}
private void ensureCapacity() {
if (size<arr.length) return;
arr= Arrays.copyOf(arr,size*2);
}
public void swap(long[] arr,int i,int j){
long temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}四、堆的應用
1、用于OS調(diào)度進程
2、topk問題
topk問題其實在現(xiàn)實生活有很多場景，比如說淘寶的好物top10等等
假如說我們要在很多數(shù)據(jù)中找到前k個最大的數(shù)? 我們有什么思路呢？
1.對所有的數(shù)據(jù)進行排序再取出前十
這種方法無疑消耗的時間成本和空間成本是是非常高的
時間復雜度達到了O（N*logN） 空間復雜度是O（N）
2.把所有的數(shù)據(jù)入堆，在取出前k個元素?
第二種方法的時間復雜度相較于第一種減少了很多 大概是O（k*logN），但我們忽略了在數(shù)據(jù)非常龐大時，堆的向下調(diào)整操作往往也需要耗費大量時間，并且空間復雜度也達到了驚人的O（N）
3.我們采用建小堆，小堆的size就是k，如果當前元素比小堆中最小元素大，我們就把它加進去，到最后堆里的元素就是topk
并且空間復雜度也只有O（k）
代碼如下：
public class Solution {
public int[] smallestK(int[] arr, int k) {
if (k==0){ //處理特殊情況，防止堆為空造成的index越界
return new int[0];
}
PriorityQueue<Integer> pq=new PriorityQueue<>(((o1, o2) -> o2-o1));
for (int i=0;i<k;i++){ //添加k個元素進入堆
pq.add(arr[i]);
}
for (int i=k;i<arr.length;i++){//維持堆中的元素是最小的k個
if (arr[i]<pq.peek()){
pq.poll();
pq.add(arr[i]);
}
}
int[] res=new int[k];//返回這k個元素
int i=0;
while (!pq.isEmpty()){
res[i++]=pq.poll();
}
return res;
}
}?3、堆排序
堆排序是一種利用堆結(jié)構(gòu)找到最值然后不斷取出進行排序，本質(zhì)上是一種選擇排序，不過由于堆找出并維持最值的時間復雜度是O（N*longN）所以他是一種高效的排序
我們把需要排序的數(shù)組看? 無序加有序的形式 一旦我們找到最值元素 我們就把它交換到最后邊
因此總的排序要進行arr.length-1次交換文章來源：http://www.zghlxwxcb.cn/news/detail-404841.html
public void swap(long[] arr,int i,int j){
long temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
public long[] heapSort(long[] nums){
//首先我們需要建立大堆，把大的元素找出并交換到最后邊
buildHeap(nums);
for (int i=0;i<nums.length-1;i++){
swap(nums,0,arr.length-1-i);
justDown(nums,arr.length-i-1,0);
}
return nums;
}
private void buildHeap(long[] nums) {
for (int i=(nums.length-2)/2;i>=0;i--){
justDown(nums,nums.length,i);
}
}?文章來源地址http://www.zghlxwxcb.cn/news/detail-404841.html
到了這里，關于淺淺理解一下堆的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
