[일반] 행님들 파이썬에서 heap이랑 deque랑 왜 시간 차이나는건가요?

[익명(222.119)]

같은 BFS 문제 같은 솔루션에

deque를 heap으로 바꿔줬을 뿐인데 시간제한 풀리네요

관련된 블로그 찾아봤는데 비전공자라 이해를 잘못하겠습니다

간단하게 질문드리면 그냥 PS풀때는 deque 말고 heapq 쓰면 되나요?

[익명(211.234)]

그리 간단하지 않음 결국 원리를 알아야함

[익명(222.119)]

아우 지끈거리네용... 공부하고 오겠슴니다..

[익명(114.206)]

우선순위큐가 필요하면 heapq 쓰고 그냥 큐가 필요하면 deque쓰면 됨

[dyp(irc2265)]

deque가 priorityqueue를 말하는거라면 heapq 쓰는게 마즘

[익명(211.243)]

댓글처럼 priortyqueue vs heapq면 전자는 쓰레딩 저장하고 후자는 저장 안해서 후자가 더 빠름 근데 파이썬은 멀티 쓰레딩 거의 안일어나서 heapq쓰는게 맞음

[익명(180.70)]

둘이 역할달라 bfs면 주로 deque 다익스트라같이 간선 가중치 있으면 heap

[익명(125.183)]

보니깐 자료구조 기초가 안되어있는거 같은데? deque 이랑 heap 이 뭔지 아는게 먼저인듯

[익명(125.183)]

deque = 스택이랑 큐를 합쳐놓은 자료구조

[익명(125.183)]

heap = 최소값이나 최댓값을 뽑는 자료구조

[익명(106.101)]

덱 앞뒤에서 데이터꺼내고 추가가 O(1) 힙큐 첫번째 데이터가 우선순위가 젤 높음 꺼내는데 O(logN) 삽입하는데 O(logN)