[자료구조] 힙 (Heap)

---

Heap

이진 트리(Binary Tree) 형태를 가지며

우선순위가 높은 요소가 먼저 나가기 위해

요소가 삽입, 삭제될 때 

바로 정렬되는 특징을 가짐

 

Heap에는 루트가 가장 큰 값이 되는 최대 힙(Max Heap)과

루트가 가장 작은 값이 되는 최소 힙(Min Heap)이 있다.

 

일반적으로 배열(array)를 활용해 구현한다.

Heap 예시

---

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. 

• 잘못되거나 부족한 부분이 있다면 언제든지 댓글 부탁드립니다 :)