push_힙 알고리즘 (즉 max - heap 조건 을 만족 시 키 고 최대 값 은 루트 노드 에 있 음)
2752 단어 heap
완전 이 진 트 리, 부모 노드 값 이 하위 노드 보다 큽 니 다.(왼쪽 노드 값 이 오른쪽 노드 값 보다 크다 는 것 은 보장 되 지 않 습 니 다.)
새 요소 삽입 시 만족 할 조건
완전 이 진 트 리 의 조건 을 만족 시 키 기 위해 새로 추 가 된 요 소 는 반드시 맨 아래 층 에 잎 노드 로 놓 고 왼쪽 에서 오른쪽 까지 의 첫 번 째 빈 칸 을 메 워 야 한다. 즉, 새로운 요 소 를 바 텀 vector 의 end () 에 삽입 하 는 것 이다.
쓰 이 는 기교
여기에 작은 기술 이 있 습 니 다. 만약 에 array 로 모든 노드 를 저장 하고 array 의 \ # 0 위치 요 소 를 보존 하면 (즉, 아래 표 시 는 1 부터) 완전한 이 진 트 리 의 특정한 노드 가 array 의 i 에 위치 할 때 왼쪽 노드 는 array 의 2i 에 위치 하고 오른쪽 노드 는 array 의 2i + 1 에 위치 하 며 아버지 노드 는 반드시 'i / 2' 에 위치 합 니 다 (i / 2 추출).array 로 완전 이 진 트 리 를 실현 하 는 방식 을 암시 적 표현 법 (implicit representation) 이 라 고 합 니 다.
SGI STL push_힙 알고리즘 구현
SGI STL 은 부모 노드 와 좌우 노드 를 계산 하 는 방식 이 위의 기법 과 약간 다 르 지만 원리 가 유사 하 다 (SGI 에서 아래 표 시 는 1 부터 라 고 볼 수 있다).
알고리즘 핵심:
// push_back() 「 」
template <class RandomAccessIterator, class Distance, class T>
void __push_heap(RandomAccessIterator first, Distance holeIndex,
Distance topIndex, T value) {
Distance parent = (holeIndex - 1) / 2; //
while (holeIndex > topIndex && *(first + parent) < value) {
// ， （ heap ）
// operator<， STL heap max-heap（ ）。
*(first + holeIndex) = *(first + parent); //
holeIndex = parent; // percolate up： ， 。
parent = (holeIndex - 1) / 2; //
} // ， heap 。
*(first + holeIndex) = value; // ， 。
} ： template <class RandomAccessIterator, class Compare>
inline void push_heap(RandomAccessIterator first, RandomAccessIterator last,
Compare comp) {
__push_heap_aux(first, last, comp, distance_type(first), value_type(first));
}
template <class RandomAccessIterator, class Compare, class Distance, class T>
inline void __push_heap_aux(RandomAccessIterator first,
RandomAccessIterator last, Compare comp,
Distance*, T*) {
__push_heap(first, Distance((last - first) - 1), Distance(0),
T(*(last - 1)), comp);
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[백준] 13334번: 철로h <= o 라는 조건이 없기 때문에 시작점과 도착점을 통일시켜주기 위해 h <= o 조건을 구현해줍니다. 도착점을 기준으로 오름차순 정렬을 합니다. 0부터 (n-1)까지 순회를 합니다. 최소힙에 시작점을 넣어주고,...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
