堆（二叉堆）總結(jié)-創(chuàng)新互聯(lián)

一、堆的種類：

（1）小根堆（小堆、最小堆）

站在用戶的角度思考問題，與客戶深入溝通，找到鶴峰網(wǎng)站設(shè)計(jì)與鶴峰網(wǎng)站推廣的解決方案，憑借多年的經(jīng)驗(yàn)，讓設(shè)計(jì)與互聯(lián)網(wǎng)技術(shù)結(jié)合，創(chuàng)造個(gè)性化、用戶體驗(yàn)好的作品，建站類型包括：成都網(wǎng)站制作、成都做網(wǎng)站、外貿(mào)營銷網(wǎng)站建設(shè)、企業(yè)官網(wǎng)、英文網(wǎng)站、手機(jī)端網(wǎng)站、網(wǎng)站推廣、域名注冊、網(wǎng)絡(luò)空間、企業(yè)郵箱。業(yè)務(wù)覆蓋鶴峰地區(qū)。

（2）大根堆（大堆、大堆）

二、一般堆的應(yīng)用和操作：

（1）插入某個(gè)節(jié)點(diǎn)

（2）刪除任意下標(biāo)節(jié)點(diǎn)

（3）替換任意下標(biāo)節(jié)點(diǎn)

堆的操作有up和down，down 和 up 都是針對下標(biāo)進(jìn)行的操作：

#include#include 
using namespace std;
const int N=100010;
int heap[N],size;

void down(int x){
    int t=x;
    if(2*x<=size && heap[t]>heap[2*x]) t=2*x; //前面的<=size是為了保證當(dāng)前節(jié)點(diǎn)存在子節(jié)點(diǎn)
    if(2*x+1<=size && heap[t]>heap[2*x+1]) t=2*x+1;
    if(x!=t){
        swap(heap[x],heap[t]);
        down(t);
    }
}

void up(int x){
    while(x/2>0 && heap[x]>heap[x/2]){
        swap(heap[x],heap[x/2]);
        x/=2;
    }
}

int main()
{
    
    return 0;
}

放一道題目：?????????AcWing 838. 堆排序（已做筆記）

三、堆的變形：

變形之后的堆與一般的堆的不同之處在于可以修改和刪除第k（k表示順序）個(gè)插入的節(jié)點(diǎn)元素，而不是下標(biāo)為k的節(jié)點(diǎn)元素

#include#include 
using namespace std;
const int N=100010;
int heap[N],size;
int cnt;//用于編號是第cnt個(gè)插入的節(jié)點(diǎn)
int ph[N];//表示第k個(gè)插入的節(jié)點(diǎn)在堆中的下標(biāo)是多少
int hp[N];//表示堆中下標(biāo)對應(yīng)的是第幾個(gè)插入的節(jié)點(diǎn)

void heap_swap(int a,int b){//a和b都表示下標(biāo)
    swap(heap[a],heap[b])；
    swap(ph[hp[a]],ph[hp[b]]);
    swap(hp[a],hp[b]);
}

void down(int x){
    int t=x;
    if(2*x<=size && heap[t]>heap[2*x]) t=2*x;
    if(2*x+1<=size && heap[t]>heap[2*x+1]) t=2*x+1;
    if(x!=t){
        heap_swap(x,t);//注意：這里使用的是下標(biāo)進(jìn)行操作，而不是像之前那樣只交換值
        down(t);
    }
}

void up(int x){
    while(x/2>0 && heap[x]

對于變形之后的堆，在進(jìn)行節(jié)點(diǎn)的刪除和修改的時(shí)候都不能只是單純的進(jìn)行值覆蓋了，而是要用heap_swap()函數(shù)對值、下標(biāo)、第cnt個(gè)插入的節(jié)點(diǎn)全部進(jìn)行交換；

放一道題目：????????AcWing 839. 模擬堆（一定要認(rèn)真看這道題?。?/p>

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

當(dāng)前文章：堆（二叉堆）總結(jié)-創(chuàng)新互聯(lián)
當(dāng)前URL：http://www.muchs.cn/article20/dpjjco.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站改版、網(wǎng)站收錄、網(wǎng)站維護(hù)、響應(yīng)式網(wǎng)站、手機(jī)網(wǎng)站建設(shè)、關(guān)鍵詞優(yōu)化

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)