mj·2021년 9월 30일
0

자료구조

목록 보기
5/6

📌힙

완전 이진트리에 있는 노드 중 키 값이 가장 큰 노드나 키 값이 가장 작은 노드를 찾기 위해서 만든 자료구조
해당 트리의 최소값, 최대값을 보려면 루트 노드만 보면 된다.

  • 장점
    노드를 추가할 때 해당 위치의 조상 노드하고만 비교하면 된다! (처리 갯수가 줄어든다)
    시간 복잡도 : logN
    ex) 10억 = 2^30개 일 경우!
    일일이 비교할 필요 없이 30번만 비교하면 된다.
  • 단점 : 삽입할 때도 logN이지만 삭제할 때도 logN 시간복잡도가 든다.
    삭제하려는 노드의 값을 마지막 위치의 노드와 바꾸고 마지막 노드를 삭제한 후 다시 정렬

💡최대 힙(max heap)

  • 키 값이 가장 큰 노드를 찾기 위한 완전 이진 트리
  • 부모 노드의 키 값 > 자식 노드의 키 값
  • 루트 노드 : 키 값이 가장 큰 노드

💡최소 힙(min heap)

  • 키 값이 가장 작은 노드를 찾기 위한 완전 이진 트리
  • 부모 노드의 키 값 < 자식 노드의 키 값
  • 루트 노드 : 키 값이 가장 작은 노드

힙 연산 - 삭제

  • 힙에서는 루트 노드의 원소만을 삭제 할 수 있다.


📌우선순위 큐 (Priority Queue)

  • 우선순위 큐를 구현하는 가장 효율적인 방법 : 힙
  • 우선순위를 가진 항목들을 저장하는 큐
  • FIFO 순서가 아니라 우선순위가 높은 순서대로 먼저 나가게 된다.

java.util.PriorityQueue()

  • Heap 자료구조
  • 원소들의 natural Ordering(=오름차순)에 따라 자동으로 Heap 유지
  • 힙이 순서대로 정렬을 할 때, Comparable과 Comparator를 통해 정렬함.
  • 반드시 모든 원소는 Comparable 인터페이스를 구현해야 함.

💡Comparable

  • 자신과 인자로 전달받는 타 원소와 비교하여 정수 리턴
  • int compareTo(T other)
    • 음수 : 타 원소가 크다
    • 0 : 둘이 같다
    • 양수 : 자신이 크다

💡Comparator

  • 비교 대상의 두 원소가 아닌 별도의 도우미 역할
  • int compare(T o1, T o2 )
    • 매개변수 두 개를 받아 두 변수를 비교한다.
    • 음수 : o2 원소가 크다
    • 0 : 둘이 같다.
    • 양수 : o1 원소가 크다.

📌힙의 활용 : 힙 정렬

  • 힙 정렬은 힙 자료구조를 이용해서 이진 트리와 유사한 방법으로 수행한다.

  • 정렬을 위한 2단계

    • 하나의 값을 힙에 삽입한다.
    • 힙에서 순차적(오름차순)으로 값을 하나씩 제거한다.
  • 힙 정렬의 시간 복잡도

    • N개의 노드 삽입 연산 + N개의 노드 삭제 연산
    • 노드 하나의 삽입과 삭제 연산은 각각 O(logN) 이다.
    • 따라서 전체 정렬은 O(NlogN)이다.
profile
내가 보려고 쓰는 블로그 :)

0개의 댓글