99클럽 코테 스터디 19일차 TIL: 힙

문제

https://www.acmicpc.net/problem/1927

풀이

힙을 구현하면 되는 문제이다.
파이썬이나, c++ stl에는 힙이나 우선순위큐가 있는 것으로 알고있는데, Swift에는 없어서 직접 구현해주어야 한다.
음.. 기억상으로 파이썬에서 최대힙? 만 지원해서 음수를 곱해서 넣거나 이런 스킬들을 사용했었던 것으로 기억이 어렴풋난다..

Swift로 힙을 구현하는 것은 해봤어서, 해당 코드로 문제를 풀이하였다.

힙 구현한 것은 이전에 포스팅 해두었었다.
https://dev-mandos.tistory.com/244

[자료구조] Heap에 대해 알아보고 구현해보기 (Swift)

 

소스코드

	struct Heap<T: Comparable> {
	private var elements: [T] = []
	private let comparer: (T, T) -> Bool
	init(comparer: @escaping (T,T) -> Bool) {
	self.comparer = comparer
	}
	mutating func insert(element: T) {
	if elements.isEmpty {
	elements.append(element)
	elements.append(element)
	return
	}
	elements.append(element)
	swimUp(index: elements.count - 1)
	}
	mutating private func swimUp(index: Int) {
	var index = index
	while index > 1 && comparer(elements[index], elements[index / 2]) {
	elements.swapAt(index, index / 2)
	index /= 2
	}
	}
	mutating func pop() -> T? {
	if elements.count < 2 { return nil }
	elements.swapAt(1, elements.count - 1)
	let deletedElement = elements.removeLast()
	diveDown(index: 1)
	return deletedElement
	}
	mutating private func diveDown(index: Int) {
	var swapIndex = index
	var isSwap = false
	let leftIndex = index * 2
	let rightIndex = index * 2 + 1
	if leftIndex < elements.endIndex && comparer(elements[leftIndex], elements[swapIndex]) {
	swapIndex = leftIndex
	isSwap = true
	}
	if rightIndex < elements.endIndex && comparer(elements[rightIndex], elements[swapIndex]) {
	swapIndex = rightIndex
	isSwap = true
	}
	if isSwap {
	elements.swapAt(swapIndex, index)
	diveDown(index: swapIndex)
	}
	}
	}
	var minHeap = Heap<Int>(comparer: <)
	for _ in 0..<Int(readLine()!)! {
	let x = Int(readLine()!)!
	if x == 0 { print(minHeap.pop() ?? 0)}
	else { minHeap.insert(element: x) }
	}

view raw 1927_최소 힙.swift hosted with ❤ by GitHub

후기

힙만 구현한다면 쉽게 풀리는 문제