[알고리즘] 힙 / 해시 테이블

힙(Heap), 우선순위 큐(Priority Queue)

Heap이란?

완전이진트리 형태의 자료구조

우선순위큐를 구현하기 위해 사용되는 자료구조

여러개의 값 중 최댓값 또는 최솟값을 찾아내는 연산이 빠르다

 

힙(Heap) : 특정 규칙을 갖는 완전 이진트리

• 최대힙 :부모 노드가 자식 노드보다 항상 크거나 같음
• 최소힙 : 부모 노드가 자식 노드보다 항상 작거나 같음

이진트리

• 각 노드가 최대 두개의 자식 노드를 가지는 트리 구조
• 완전 이진 트리 : 말단 노드를 제외하고 모든 노드가 2개의 자식을 갖고있는 이진트리

 

우선순위 큐

우선순위 큐란?

Queue는 먼저 들어온 데이터가 나가는 FIFO(선입선출) 형식의 구조

우선순위 큐(Priority Queue)는 들어온 순서와는 상관없이 우선순위가 높은 데이터가 먼저 나가는 자료구조

우선순위 큐 (Priority Queue)는 힘(Heap)을 이용하여 구현하는것이 가장 효율적

 

Priority Queue 특징

1. 높은 우선순위의 요소를 먼저 꺼내서 처리하는 구조
2. 내부 요소는 힙으로 구성되어 있는 이진트리 구조로 이루어져 있다
3. 우선순위를 중시해야 하는 상황에서 쓰인다

 

Priority Queue 선언

// 낮은 숫자가 우선순위인 int형 우선순위 큐 선언
PriorityQueue<Integer> priorityQueueLowest = new PriorityQueue<>();
priorityQueueLowest.offer(1);
priorityQueueLowest.offer(2);
priorityQueueLowest.offer(3);
priorityQueueLowest.poll();
// 1


//높은 숫자가 우선순위인 int 형 우선순위 큐 선언
PriorityQueue<Integer> priorityQueueHighest = new PriorityQueue<>(Collections.reverseOrder());
PriorityQueue<Integer> priorityQueueHighest = new PriorityQueue<>((a, b) -> b - a); // 최대 힙

priorityQueueHighest.offer(1);
priorityQueueHighest.offer(2);
priorityQueueHighest.offer(3);
priorityQueueHighest.poll();
// 5

 

 

해시 테이블 (Hash Table)

키(Key) 를 값(value) 에 매핑할수 있는 구조

데이터를 빠르게 검색, 추가, 삭제 할수 있음, O(1)의 시간 복잡도

해시 함수(Hash Function)를 사용하여 키를 해시값(Hash Value)로 변환

 

해시함수(Hash Function)

• 결정성
• 고정된 출력크기
• 빠른 계산
• 균일한 분포
• 충동 저항성

 

충동관리 (Collision Handling)

• 해시 함수는 서로 다른 두 키가 동일한 해시 값을 반환시 충돌
• 체이닝( Chaining ) : 배열의 각 인덳스에 충돌된 모든 요소를 저장
• 오픈 어드레싱 (Open Addressing) : 충돌이 발생하면 다른 빈 슬롯을 찾아 값을 저장
  • 선형 탐사(Linear Probing), 이차 탐사(Quadratic Probing), 이중 해싱(Double Hashing) 등

 

해시선언

HashMap<Integer, String> hashTable = new HashMap<>();

// 삽입
hashTable.put(1, "고양이");
hashTable.put(2, "강아지");

// 검색
hashTable.get(1); // key를 통해 검색 - O(1) 한번에 찾기 가능

// 삭제
hashTable.remove(1);

 

 

HashMap

[Java] Map - HashMap

 

[Java] HashMap에서 최대값/최소값 key, value 찾기