make_heap 예제

std::push_heap 및 std::pop_heap은 힙 요소에 대한 순서 관계를 정의하기 위해 비교 함수를 입력으로 사용할 수도 있습니다. 예를 들어, 아래 예제에서는 힙을 최소 힙으로 변환하는 한 가지 방법을 보여 주며 make_heap()은 시퀀스를 힙으로 변환하는 데 사용됩니다. 힙은 최고 또는 최저) 요소를 가리키고 O(1) 시간에 액세스하는 데이터 구조입니다. 다른 모든 요소의 순서는 특정 구현에 따라 다르지만 전체적으로 일관되게 유지됩니다. 이 함수는 헤더 “알고리즘”에 정의되어 있습니다. make_heap() 함수의 두 가지 구현이 있습니다. 둘 다 이 기사를 통해 설명되어 있습니다. 구문 1 : make_heap (iter_first, iter_last) 예를 들어 컬렉션이 힙인 경우 std::is_heap_until 컬렉션의 끝을 반환합니다. 첫 번째 요소가 두 번째 요소보다 작으면 힙 속성이 처음부터 끊어진 이후 첫 번째 위치를 반환합니다. 이 게시물의 1 부에서 언급했듯이 먼저 배열에 힙 요소를 저장한 다음 heapify 메서드를 사용하여 배열 요소를 다시 정렬하여 유효한 힙으로 변환하는 경우 $O(nlog(n))$가 아닌 시간 $O 힙을 생성할 수 있습니다.

이것이 std::make_heap이 하는 일입니다: 최대 힙에서 가장 큰 요소는 루트에 있습니다. 따라서 힙의 예는 다음과 같습니다: 서로 비교할 수 있는 다양한 개체가 있는 경우 이 범위를 std::make_heap을 사용 하 여 최대 힙으로 다시 정렬할 수 있습니다. STL이 힙을 나타내는 방법입니다: 힙은 std:::vector에 저장될 수 있으며, 예를 들어 요소는 위와 같이 서로 나란히 배치됩니다. 이전 게시물에서 std::priority_queue 컨테이너는 힙에 있어야 하는 대부분의 기능을 제공 하므로 도입 되었습니다. 이 게시물은 앞에서 제시한 접근 방식보다 모듈방식이 적고 힙 요소에 대한 캡슐화를 제공하지 않으므로 더 유연하지만 소프트웨어 엔지니어링 관점에서 는 덜 깨끗한 힙으로 작업하는 또 다른 방법을 제공합니다. 이 방법은 힙 요소를 저장하고 STL 함수std::make_heap, std::push_heap 및 std::pop_heap을 사용하여 컨테이너의 요소를 유효한 힙으로 정렬하기 위해 임의 액세스 이터레이터(예: std:::vector)가 있는 모든 컨테이너를 사용하는 것으로 구성됩니다. 그런 다음 유효한 힙을 유지하면서 컨테이너에서 요소를 푸시하고 팝합니다. 다음에, 우리는이 작업을 수행 할 수있는 방법에 대한 완전한 예를 제공 할 것입니다. 여기에 표시된 기술은 배열에 구현된 힙 데이터 구조의 내부 작업 중 일부를 노출합니다(가장 일반적인 기술). 예를 들어 마지막 힙 요소 다음에 배열 위치에 배치한 다음 올바른 위치에 도달할 때까지 이 요소를 “버블링”하여 힙에 새 요소를 삽입합니다.

Share on Facebook