[자료구조론]힙 & 덱

힙

 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리

       1)부모노드와 자식노드간에 절대적 대소관계 성립

       2)키값의 대소관계는 오로지 부모노드와 자식노드 간에만 성립(형제와는 대소관계 정해지지 않음)

 최소힙, 최대힙 두가지 종류가 있다. 

힙에서의 삽입 연산: 삽입된 값을 완전 이진트리에서의 맨 마지막 위치에 보낸다. 그 후 힙의 성질에 맞ㄱ게 위치를 재배열한다.

 

힙에서의 삭제 연산: 루트노드에 한해서만 정의된다. 루트노드를 삭제한 후, 완전 이진트리의 맨 마지막 노드를 루트로 보낸 뒤 힙속성에 맞게 위치를 재배열한다.

 

   성능

    Binary min heap에서, heap을 구축한 것을 전제로 했을 때

    Find Min : O(1)  //최소값 탐색

    Delete Min: O(log n) //최소값 삭제

    Insert : O(log n) //새로운 원소 삽입

 

  응용 

   우선 순위 큐, 힙 정렬을 구현하는데 유용하게 쓰인다. 

    

 

덱(Dequeue)

 Doubled Ended Queue의 준말로, 양쪽에서 모두 입력과 출력이 가능하다. 스택과 큐에 비해 자유도가 높은 자료구조이다. 덱은 스택과 큐의 성질을 모두 가지고 있다.

 

 

각 잡업들의 시간복잡도는 O(1)이지만, 전체 사이즈를 알아보는 연산에 국한해서는 배열로 구현시 O(1), 연결리스트로 구현 시 O(n)이 된다. 

 

#덱의 ADT 

 create(MAX)

 init(dq): 덱을 초기화한다. front,rear 멤버 변수를 각각 0으로 설정ㅎ나다. 

 is_empty(dq)

add_front(dq,e)

add_rear(dq,e)

delete_front(dq)

delete_rear(dq)

get_front(dq)

get_rear(dq)