안녕하세요?
이번 시간에는 파이썬에서의 힙에 대해 알아보려고 해요.
이번 시간 내용은 큐에 대해 알고 있어야 글 내용을 잘 이해하실 수 있어요.
큐가 무엇인지 궁금하시다면 제가 이전에 올린 스택과 큐라는 글을 참고해주세요.
그럼 지금부터 힙에 대해 자세히 알아볼게요!!
힙이란?
힙은 큐 구조에서 우선순위를 더한 개념이에요.
우선순위는 어떤 것을 먼저 차지하거나 사용할 수 있는 차례나 위치를 말하죠.
즉, 힙 자료구조는 큐를 기반으로 작동하지만, 정해진 우선순위에 따라서 가장 작은 숫자나, 가장 큰 숫자를 순서대로 꺼내 올 수 있는 다양한 함수를 제공해요.
힙의 문법
파이썬에서는 힙에 대한 내장 라이브러리를 추가 설치 없이도 제공하고 있어요.
import heapq
heap = []힙으로 이용할 리스트 를 만들어줬어요.
heapq.heappush(heap,5) #[5]
heapq.heappush(heap,3) #[3,5]
heapq.heappush(heap,7) #[3,5,7]
heapq.heappush(heap,1) #[1,3,5,7,]첫번째로 빈 리스트에 5를 추가해줬어요.
이땐 아무것도 없기 때문에 단순 추가돼요.
두 번째로 3을 추가해주는데, 힙 속성이 최소 힙이기 때문에 작은 숫자가 앞으로 와야 해요.
따라서 3과 5의 자리를 바꿔요.
=> [3, 5]
이어서 7을 추가해주는데, 7은 힙 속성에 맞기 때문에 그냥 추가해요.
=>[3, 5, 7]
마지막으로 1을 추가해요.
힙 속성에 맞지 않기 때문에 0번 인덱스와 마지막 인덱스를 비교해 조건이 맞으면 교환해요.
=> [1, 5 ,7, 3]
다음으로 마지막 인덱스와 1번 인덱스를 비교해서 조건에 맞는다면 교환해요.
=>[1, 3, 7, 5]
마지막으로 2번 인덱스와 마지막 인덱스를 비교해주는데 리스트를 출력해주면 여전히 [1, 3, 7, 5]로 출력돼요.
이는 heapq라이브러리의 특징으로 출력된 리스트만 보고는 정확한 힙의 형태를 알 수 없어요.
하지만 실제로는 최소 힙 속성을 유지하며 정렬이 이루어져요.
=> [1, 3, 5, 7]
힙이 제공하는 여러 기능으로는 heapq.heappop(변수이름) 코드를 이용해 가장 작은 요소를 제거하고 반환하는 기능이 있고, heapq.nsmallest(n, 변수이름)코드로 가장 작은 수 n 개를 꺼내오는 기능, heapq.nlargest(n, 변수이름)코드를 이용해 가장 큰 수 n 개를 꺼내오는 기능도 있어요.
힙의 활용
힙은 최소 값, 최대 값을 쉽게 찾을 수 있도록 도와주고, 다양한 작업을 우선순위별로 실행해 작업효율성을 높여줄 수 있어요.
여러분도 코딩을 통해 여러분만의 프로그램을 만들어보세요!
