일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
Tags
- 정규표현식
- 코딩공부
- 코드스테이츠
- select
- array
- 프로그래머스
- 역행자
- Algorithms
- join
- SQL
- 코딩테스트
- array.slice()
- Programmers
- 자바스크립트
- 코플릿
- for문
- 재귀함수
- 최강의 인생
- Developer_JoyKim
- 알고리즘
- Where
- array.push()
- 블록체인
- 개발자의 책장
- Hackerrank
- MySQL
- 개발자_조이킴
- node.js
- 배열
- JavaScript
Archives
- Today
- Total
CodingSpace
[자료구조] 힙 (Heap) 본문
Heap
이진 트리(Binary Tree) 형태를 가지며
우선순위가 높은 요소가 먼저 나가기 위해
요소가 삽입, 삭제될 때
바로 정렬되는 특징을 가짐
Heap에는 루트가 가장 큰 값이 되는 최대 힙(Max Heap)과
루트가 가장 작은 값이 되는 최소 힙(Min Heap)이 있다.
일반적으로 배열(array)를 활용해 구현한다.
Heap - 요소 추가 알고리즘
①: Heap에 요소가 추가될 때는 트리의 가장 마지막 정점에 위치시킨다.
②: 요소를 추가한 후 부모 정점보다 우선순위가 높다면 부모 정점과 순서를 바꾼다.
①번 ②번 과정을 반복하면 가장 우선순위가 높은 정점이 루트가 된다.
위의 알고리즘을 javascript 코드로 구현하면 아래와 같다.
// javascript로 구현한
// Heap 요소 추가 알고리즘 (MaxHeap)
class MaxHeap {
constructor() {
// 배열로 이진트리를 구성할 때
// 1번 인덱스를 루트로 설정한 경우 계산이 더 편함
this.heap = [null];
}
push(value) {
// 배열 맨 끝에 요소를 추가함
this.heap.push(value);
// 추가된 요소의 인덱스
let currentIndex = this.heap.length - 1;
// 추가된 요소의 부모의 인덱스
let parentIndex = Math.floor(currentIndex / 2);
// currentIndex가 루트 정점이 아니고
// 삽입된 값이 부모 정점보다 크면 -> 계속해서 정렬
while (currentIndex !== 0 && this.heap[parentIndex] < value) {
// 부모 정점의 값을 임시로 담아두고
const temp = this.heap[parentIndex];
// 부모 정점과 삽입된 값의 위치를 바꾼다
this.heap[parentIndex] = value;
this.heap[currentIndex] = temp;
// currentIndex 업데이트
currentIndex = parentIndex;
// parentIndex 업데이트
parentIndex = Math.floor(currentIndex / 2);
}
}
}
python 코드로 구현하면 아래와 같다.
class Heap:
def __init__(self, data):
self.heap_array = list()
# 편의상 맨 앞에 인덱스에 None 값을 넣어준다 -> 루트 노드 인덱스가 1이 되도록
self.heap_array.append(None)
self.heap_array.append(data)
# Swap이 필요한지 확인하는 함수 (필요 O -> True 반환, 필요 X -> False 반환)
def move_up(self, insert_idx):
# 삽입한 데이터가 루트 노드인 경우 False 반환
if insert_idx <= 1:
return False
# 부모 인덱스 계산
parent_idx = insert_idx // 2
# (최대힙) 부모 노드의 값보다 삽입한 데이터의 값이 큰 경우 -> True 반환
if self.heap_array[insert_idx] > self.heap_array[parent_idx]:
return True
else:
return False
# 데이터 삽입 함수
def insert(self, data):
# 먼저 맨 끝에 데이터를 넣어준다
self.heap_array.append(data)
# 현재 삽입한 인덱스
insert_idx = len(self.heap_array) - 1
# Swap 루프
while self.move_up(insert_idx):
# 부모 인덱스
parent_idx = insert_idx // 2
# 부모 노드와 Swap
self.heap_array[insert_idx], self.heap_array[parent_idx] = self.heap_array[parent_idx], self.heap_array[insert_idx]
# 현재 인덱스 업데이트
insert_idx = parent_idx
Heap - 요소 삭제 알고리즘
요소 제거는 루트 정점만 가능하다.
①: 루트 정점이 제거된 후 가장 마지막 정점이 루트에 위치한다.
②: 루트 정점의 두 자식 정점 중 더 우선순위가 높은 정점과 바꾼다.
①번 ②번 과정을 반복하면서 두 자식 정점이 우선순위가 더 낮을 때 까지 반복한다.
위의 알고리즘을 javascript 코드로 구현하면 아래와 같다.
// javascript로 구현한
// Heap 제거 추가 알고리즘 (MaxHeap)
class MaxHeap {
constructor() {
// 배열로 이진트리를 구성할 때
// 1번 인덱스를 루트로 설정한 경우 계산이 더 편함
this.heap = [null];
}
pop() {
// 루트 정점의 값을 제거한다.
let returnValue = this.heap[1];
// 맨 마지막 정점의 값을 루트 정점에 위치시킨다.
this.heap[1] = this.heap.pop();
let currentIndex = 1;
let leftIndex = 2;
let rightIndex = 3;
// 현재 정점의 값이
// 왼쪽 자식 정점의 값보다 작거나
// 오른쪽 자식 정점의 값보다 작으면
// while 루프문 계속 실행
while (
this.heap[currentIndex] < this.heap[leftIndex] ||
this.heap[currentIndex] < this.heap[rightIndex]
) {
// 오른쪽 자식 정점의 값이 왼쪽 자식 정점의 값보다 큰 경우
if (this.heap[leftIndex] < this.heap[rightIndex]) {
// 현재 정점의 값을 임시로 저장
const temp = this.heap[currentIndex];
// 현재 정점에 오른쪽 자식 정점의 값을 위치시킴
this.heap[currentIndex] = this.heap[rightIndex];
// 오른쪽 자식 정점에 현재 정점의 값을 위치시킴
this.heap[rightIndex] = temp;
// 현재 정점의 위치 업데이트
currentIndex = rightIndex;
} else {
// 현재 정점의 값을 임시로 저장
const temp = this.heap[currentIndex];
// 현재 정점에 왼쪽 자식 정점의 값을 위치시킴
this.heap[currentIndex] = this.heap[leftIndex];
// 왼쪽 자식 정점에 현재 정점의 값을 위치시킴
this.heap[leftIndex] = temp;
// 현재 정점의 위치 업데이트
currentIndex = leftIndex;
}
// 왼쪽 정점의 위치 업데이트
leftIndex = currentIndex * 2;
// 오른쪽 정점의 위치 업데이트
rightIndex = currentIndex * 2 + 1;
}
}
}
References.
- 코딩테스트 광탈 방지 A to Z: JavaScript (이선협)
For Developer.
- 잘못되거나 부족한 부분이 있다면 언제든지 댓글 부탁드립니다 :)
'자료구조 및 알고리즘' 카테고리의 다른 글
[알고리즘] - 아레토스테네스의 체 (소수 찾기) (0) | 2023.05.29 |
---|---|
[자료구조] 큐 (Queue) (0) | 2023.05.23 |
Comments