1. 힙(Heap) 자료구조

• 정의: 힙은 우선순위 큐를 구현하기 위해 고안된 완전 이진 트리 형태의 자료구조
• 장점: 여러 개의 값 중 최댓값 또는 최솟값을 빠르게 찾을 수 있다.
• 특징:
  • 부모 노드와 자식 노드 간에 대소 관계가 성립
  • 힙의 종류:
    1. 최대 힙(Max-Heap): (부모노드 >= 자식노드) ![[Pasted image 20240708203717.png | 400]]
    2. 최소 힙(Min-Heap): (부모노드 <= 자식노드)
       • ![[Pasted image 20240708191256.png | 400]]
• 함수 구현:
  • Min-Heapify():
    • 부모 노드로 올라가며, 부모보다 자신의 값이 더 작은 경우 위치를 교체(위가 작게)
    • 새로운 원소가 삽입되면, 시간 복잡도 O(log N)으로 힙의 성질을 유지

2. 큐(Queue) 자료구조란?

• 정의: 큐는 First In First Out(FIFO) 구조를 가지는 자료구조
• 특징: 먼저 들어간 데이터가 먼저 나오는 구조

3. 우선순위 큐(Priority Queue)

• 정의: 들어간 순서에 상관 없이, 우선순위가 높은 데이터가 먼저 추출되는 자료구조
• 특징:
  • 우선순위가 가장 높은 데이터를 가장 먼저 삭제
  • 예시: 물건 데이터를 자료구조에 넣었다가 가치가 높은 물건부터 꺼내서 확인하는 경우.
• 구현 방법:
  1. 리스트를 이용한 구현:
     • 데이터를 넣은 후 가장 큰 데이터를 뽑아 추출합니다.
     • 시간 복잡도:
       • 삽입 시간: O(1) (단순히 리스트의 끝에 삽입)
       • 삭제 시간: O(N) (우선순위가 높은 데이터를 찾기 위해)
  2. 힙을 이용한 구현:
     • 시간 복잡도:
       • 삽입 시간: O(log N)
       • 삭제 시간: O(log N)
     • 배열이나 연결 리스트보다 힙을 이용하여 구현하는 것이 효율적입니다.

4. 스택(Stack)

• 정의: 스택은 가장 나중에 삽입된 데이터가 먼저 추출되는 자료구조
• 특징: Last In First Out(LIFO) 구조를 가짐
  1. 완전 이진 TREE : 위에서부터 2개씩 계속 나아가는~
  2. 부모 NODE < 자식 NODE : 윗쪽이 아래쪽보다 작아야한다. 위로 갈수록 숫자가 작다.