C++ heap

학습 목표

- <algorithm> 헤더파일에 속한 make_heap, pop_heap, push_heap, sort_heap 각각의 용법을 파악한다.

---

<전체 코드>

// range heap example
#include <iostream>     // std::cout
#include <algorithm>    // std::make_heap, std::pop_heap, std::push_heap, std::sort_heap
#include <vector>       // std::vector

int main () {
  int myints[] = {10,20,30,5,15};
  std::vector<int> v(myints,myints+5);

  std::make_heap (v.begin(),v.end());
  std::cout << "initial max heap   : " << v.front() << '\n';

  std::pop_heap (v.begin(),v.end()); v.pop_back();
  std::cout << "max heap after pop : " << v.front() << '\n';

  v.push_back(99); std::push_heap (v.begin(),v.end());
  std::cout << "max heap after push: " << v.front() << '\n';

  std::sort_heap (v.begin(),v.end());

  std::cout << "final sorted range :";
  for (unsigned i=0; i<v.size(); i++)
    std::cout << ' ' << v[i];

  std::cout << '\n';

  return 0;
}

 

1) make_heap

- Default 는 max_heap이다. 

- 첫 번째 요소가 최대값 임을 요구하므로 나머지 뒷부분은 크기순으로 정렬되지 않아도 상관없다.

  std::make_heap (v.begin(),v.end());
  std::cout << "initial max heap   : " << v.front() << '\n';
  
     30
   /	\
  20    15
 / \    
10  5

 

2) pop_heap

- 가장 큰 값을 맨 자식 노드와 교환한다, 그리고 부모 노드를 재 정렬한다, O(logN)

- 그렇기 때문에 pop_back을 수행 해줘야 완전한 pop이 된다.

  std::pop_heap (v.begin(),v.end()); v.pop_back();
  std::cout << "max heap after pop : " << v.front() << '\n';

(1) pop_heap(v.begin(),v.end())
     5
   /	\
  20    15
 / \    
10  30

(2) pop_heap(v.begin(),v.end())
     20
   /	\
  10    15
 / \    
5  30

(3) v.pop_back()
     20
   /	\
  10    15
 /    
5

 

3) push_heap

-  넣고자 하는 값을 가장 뒤에 넣는다. 그리고 힙을 재 정렬한다, O(logN)

- 정렬하고 빼는 pop_heap과 달리 먼저 넣고 정렬한다. 

  v.push_back(99); std::push_heap (v.begin(),v.end());
  std::cout << "max heap after push: " << v.front() << '\n';
  
(1) v.push_back(99)
     20
   /	\
  10    15
 /  \  
5   99

(2) v.push_heap(v.begin(),v.end())
     99
   /	\
  20    15
 /  \  
5   10

 

4) sort_heap

- 오름 차순 재정렬한다. 

 std::sort_heap (v.begin(),v.end());

     5
   /	\
  10    15
 /  \  
20   99