최대힙 C++로 구현하기

동적 배열을 사용하여 C++에서 최대 힙 데이터 구조 구현.

다음 메서드는 MaxHeap의 공용 인터페이스에서 사용할 수 있습니다.

-> MaxHeap() : 기본 생성자

-> MaxHeap(int _capacity) : 주어진 크기의 용량을 힙에 할당한다.

-> void insert(k const key, v const value) : 힙에 새로운 <key,value> 쌍을 삽입합니다. 키는 힙 순서를 유지하는 데 사용됩니다.

-> void getMax(v & value) : 참조로 전달된 매개변수를 통해 키가 최대인 값을 반환합니다.

-> void deleteMax() : 키가 최대인 힙 항목을 삭제합니다.

-> bool isEmpty() const : 힙에 항목이 없으면 true를 반환하고 그렇지 않으면 false를 반환합니다.

-> void deleteAll() : 힙을 완전히 파괴합니다. 용량은 0으로 설정되고 힙의 배열은 nullptr로 설정됩니다.

-> ~MaxHeap() : 소멸자

-> void doubleCapacity() : 힙 용량을 두 배로 늘립니다. 예를 들어 현재 힙의 용량이 10이라면 이 함수를 호출한 후 용량은 20이 됩니다. 이 메서드는 힙이 가득 찼을 때 용량을 늘리기 위해 삽입 메서드에서 사용합니다.

-> void shiftUp(int index) : 단일 재귀 호출에서 해당 인덱스에 저장된 항목의 키가 부모 키보다 크면 한 단계 위로 이동하는 재귀 메서드입니다. 삽입 방법은 이 방법을 사용하여 키가 최대인 경우 새 항목을 루트로 재귀적으로 이동합니다.

-> void shiftDown(int index) : 단일 재귀 호출에서 해당 항목의 키가 자식 키보다 작은 경우 지정된 인덱스에 저장된 항목을 한 단계 아래로 이동하는 재귀 메서드입니다. deleteMax 메소드는 이 메소드를 사용합니다. 최대 항목(인덱스 0에 있는 항목)을 삭제하기 위해 deleteMax 메소드는 먼저 마지막 항목을 인덱스 0으로 이동한 다음 인덱스 0부터 시작하여 shiftDown 메소드를 호출하여 마지막 항목을 적절한 위치로 재귀적으로 아래로 이동합니다.