一、堆的種類：

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

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

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

二、一般堆的應用和操作：

（1）插入某個節(jié)點

（2）刪除任意下標節(jié)點

（3）替換任意下標節(jié)點

堆的操作有up和down，down 和 up 都是針對下標進行的操作：

#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是為了保證當前節(jié)點存在子節(jié)點
    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表示順序）個插入的節(jié)點元素，而不是下標為k的節(jié)點元素

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

void heap_swap(int a,int b){//a和b都表示下標
    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);//注意：這里使用的是下標進行操作，而不是像之前那樣只交換值
        down(t);
    }
}

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

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

放一道題目：????????AcWing 839. 模擬堆（一定要認真看這道題！）

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

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

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

廣告

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