[Jungle][TIL] 240325 파이썬 정렬 lambda 사용, 힙 자료구조 (최대 힙, 최소 힙)

파이썬 정렬 람다 lambda함수

백준 1181번 단어 정렬

sort(), sorted()를 활용할 때 key = lambda : 정렬 기준 를 활용하면 특정 기준에 맞게 정렬할 수 있다.

set_lst.sort(key= lambda x: (len(x), x))

힙(heap)?

• 우선순위 큐를 위해 만들어진 구조
• 완전이진트리 형태의 자료구조
• 최댓값과 최솟값을 빠르게 찾기 위해 고안된 자료구조

최대힙

: 각 노드의 키 값이 그 자식노드의 키 값보다 작지 않은 힙
key(T.parent(v)) > key(v)

최소힙

:각 노드의 키 값이 그 자식노드의 키 값보다 크지 않은 힙
key(T.parent(v)) < key(v)

파이썬에서 힙 자료구조 구현 - 백준 11279번

import sys
import heapq
input = sys.stdin.readline

N = int(input())
heap = []

for i in range(N):
    x = int(input())
    #x가 자연수인 경우  - 값을 추가

    if x != 0:
        heapq.heappush(heap, -x)
        #기본은 그냥 최소힙 -> 마이너스를 붙여 최대힙으로 구현한다.
    #x가 0인 경우 - 배열에서 가장 큰 값 출력/ 그 값을 배열에서 제거

    else:
        if len(heap) == 0:
            print(0)
        else:
            print(heapq.heappop(heap)*-1)

참고) https://hocheon.tistory.com/70