Heap, Hash Table

힙(Heap)

힙은 완전 이진 트리의 일종, 우선순위 큐를 구현하기 위해 사용되는 자료구조

• 완전이진트리: 자식노드가 두개씩 있는 것

힙의 특성

• 힙은 각 노드가 하위 노드보다 큰(또는 작은) 우선순위를 가진다
• 최대 힙(Max Heap)에서는 부모 노드가 자식 노드보다 항상 크고, 최소 힙(Min Heap)에서는 부모 노드가 자식 노드보다 항상 작다
• 우선 순위 큐 구현에 사용되는 자료구조

우선순위 큐 구현

import java.util.PriorityQueue;

PriorityQueue<Integer> minHeap = new PriorityQueue<>(); // 최소 힙
minHeap.offer(5);
minHeap.offer(1);
minHeap.offer(3);
System.out.println(minHeap.poll()); // 1

PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a); // 최대 힙
maxHeap.offer(5);
maxHeap.offer(1);
maxHeap.offer(3);
System.out.println(maxHeap.poll()); // 5

• 디폴트는 오름차순으로 저장된다
• 람다식을 이용하거나 comperator를 재정의하면 원하는대로 변경 가능하다

해시테이블 (Hash Table)

해시테이블은 키를 값에 매핑할 수 있는 구조로, 데이터를 빠르게 검색, 추가, 삭제할 수 있다

해시 테이블의 특성

• 해시 함수를 사용하여 키를 해시 코드로 변환하고, 이 코드를 사용하여 값을 저장하거나 검색할 수 있다
• 평균적으로 O(1)의 시간 복잡도로 데이터에 접근할 수 있다

해시 테이블 구현

import java.util.HashMap;

HashMap<String, Integer> map = new HashMap<>();
map.put("apple", 3);
map.put("banana", 5);
map.put("cherry", 2);

System.out.println(map.get("banana")); // 5

해시테이블은 다른 자료구조에서 가질 수 없는 낮은 시간복잡도를 가지고있어서 활용도가 높다