힙(HEAP)

자료구조 삭제되는 요소
스택(Stack) 가장 최근에 들어온 데이터
큐(Quene) 가정 먼저들어온 데이터
우선순위 큐(Priority Quene) 가장 우선순위가 높은 데이터

자료구조 ‘힙(heap)’이란?

  • 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다.

  • 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다.

  • 힙은 일종의 반정렬 상태(느슨한 정렬 상태) 를 유지한다.

    • 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다
    • 간단히 말하면 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리를 말한다.

  • 힙 트리에서는 중복된 값을 허용한다. (이진 탐색 트리에서는 중복된 값을 허용하지 않는다.)

  • ex) img

    더 맵게

1차 답안

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def solution(scoville, k):
    total = 0 
    cnt = 0 

    while(k > total):
        cnt = cnt + 1
        
        if len(scoville) == 0:
            return -1
        
        scoville.sort()
        
        if total >= k:
            break
        else:
            total = scoville.pop(0) + (scoville.pop(0) * 2)
            scoville.append(total)
    return cnt

결과 오류

2차 답안

1
2
3
4
5
6
7
8
9
10
def solution(scoville, k):
    cnt = 0 
    while min(scoville) < k:
        scoville.sort()
        try:
            scoville.append(scoville.pop(0) + (scoville.pop(0) * 2))
        except IndexError:
            return -1
        cnt += 1
    return cnt

효율성 테스트 통과 x

min(iterable1, iterable2, ...)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
a = [1, 2, 3] 
print(min(a)) 
# 반환 : 1 
b = 'BlockDMask' 
print(min(b)) 
# 반환 : 'B'
c = 1 
print(min(c)) 
# error : 'int' object is not iterable 
d = (6, 5, 4, 2) 
print(min(d)) 
# 반환 : 2 
e = [3, 4, 5, 'a', 'b', 'c'] 
print(min(e)) 
# error : str 타입과 int 타입은 비교할 수 없기 때문

3차답안

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import heapq

def solution(scoville, k):
    heap = []
    
    for i in scoville:
        heapq.heappush(heap,i)
        
    cnt = 0
    
    while heap[0] < k:
        try:
            heapq.heappush(heap, heapq.heappop(heap) + (heapq.heappop(heap) * 2))
        except IndexError:
            return -1
        cnt += 1
    return cnt

heapq

1
2
3
4
5
heapq.heappush(heap, item)
힙 불변성을 유지하면서, item 값을 heap으로 푸시합니다.

heapq.heappop(heap)
힙 불변성을 유지하면서, heap에서 가장 작은 항목을 팝하고 반환합니다. 힙이 비어 있으면, IndexError가 발생합니다. 팝 하지 않고 가장 작은 항목에 액세스하려면, heap[0]을 사용하십시오.

디스크 컨트롤러

1차답안

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def solution(jobs):
    answer = 0
    start = 0
    length = len(jobs)

    jobs = sorted(jobs, key=lambda x: x[1])

    while len(jobs) != 0:
        for i in range(len(jobs)):
            if jobs[i][0] <= start:
                start += jobs[i][1]
                answer += start - jobs[i][0]
                jobs.pop(i)
                break

            if i == len(jobs) - 1:
                start += 1

    return answer//length

list.sort() vs sorted()

list.sort() sorted()
리스트 내부에서 정렬 리스트 외부에서 정렬
None 리턴 정렬된 값 리턴
List iterable(dictionary/list/tuple)

2차답안

heapq로 다시풀기

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
import heapq

def solution(jobs):
    n = len(jobs)
    time, end , quene = 0, -1 , []
    count = 0
    answer = 0 

    while count < n:

        for job in jobs:
            if end < job[0] <= time:
                answer += (time - job[0])
                heapq.heappush(quene, job[1])

        if len(quene) > 0:
            answer += len(quene) * quene[0]
            end = time
            time += heapq.heappop(quene)
            count += 1
            
        else:
            time += 1

    return answer//n

이중우선순위큐

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import heapq

def solution(operations):
    answer = []
    for operation in operations:
        oper = operation.split(" ")
        if oper[0] == "D":
            if len(answer) == 0:
                pass
            else:
                if oper[1] == "1":
                    # heapq._heappop_max(answer)
                    answer.remove(max(answer))
                elif oper[1] == "-1":
                    heapq.heappop(answer)
        elif oper[0] == "I":
            heapq.heappush(answer, int(oper[1]))
            
    if len(answer) == 0:
        return [0,0]
    else:
        return [max(answer), min(answer)]

_heappop_max