두 갈래 더미 의 삽입 과 삭제
1. 더 미 는 완전 이 진 트 리 입 니 다. 2. 일반적으로 더 미 는 일반적으로 가장 크 거나 가장 작은 것 입 니 다. 여기 서 가장 작은 것 은 우선 순 위 를 말 합 니 다. 전통 적 인 의미 의 크기 가 아 닙 니 다. 3. 더 미 는 보통 두 가지 형식 이 있 습 니 다. 큰 뿌리 더미 와 작은 뿌리 더미, 큰 뿌리 더 미 는 더 미 를 쌓 는 우선 순위 가 가장 크 고 작은 뿌리 더 미 는 더 미 를 쌓 는 우선 순위 가 가장 작은 것 입 니 다.
두 무더기 의 조작
1. 삽입 더미 의 삽입 은 새로운 요 소 를 더미 밑 에 놓 고 이 위치 에 맞 는 지 판단 하 는 것 입 니 다. 만약 에 맞 으 면 거기에 버 리 는 것 입 니 다. 만약 에 맞지 않 으 면 아버지 와 교환 하고 재 귀적 으로 일치 할 때 까지 삽입 하면 완 성 된 것 입 니 다.
void swap(int &x,int &y)//
{int t=x;x=y;y=t;}
int heap[N];//
int siz;//
void push(int x)//
{
heap[++siz]=x;
now=siz;
//
while(now)
{// ，
long long nxt=now>>1;//
if(heap[nxt]>heap[now])
swap(heap[nxt],heap[now]);// ，
else
break;// ，
now=nxt;//
}
return;
}2. 삭제 코드 에서 삭제 하 는 것 은 쌓 인 지붕 과 쌓 인 바닥 을 직접 교환 한 다음 에 교 환 된 쌓 인 지붕 을 그의 하위 노드 와 계속 교환 하 는 것 입 니 다. 이 더미 가 다시 쌓 인 성질 에 부합 할 때 까지.
void pop()
{
swap(heap[siz],heap[1]);siz--;// ，
int now=1;
while((now<<1)<=siz)
{//
int nxt=now<<1;//
if(nxt+1<=siz&&heap[nxt+1]<heap[nxt])
nxt++;//
if(heap[nxt]<heap[now])
swap(heap[now],heap[nxt]);//
else
break;//
now=nxt;//
}
}확장 은 c + + 에서 우리 에 게 용 기 를 제공 합 니 다. 우선 대기 열 은 이러한 이 진 더미 문 제 를 해결 하 는 것 을 쉬 워 지게 합 니 다. 여 기 는 상세 하지 않 습 니 다. 나중에 배 워 서 다시 이용 하 겠 습 니 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
간단한 애니메이션 대기열 모델텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
