힙은 우선순위 큐를 위해 만들어진 자료구조임
우선순위 큐 : 우선순위의 개념을 큐에 도입한 자료구조. 배열,연결리스트,힙으로 구현(힙이 가장 효율적!)
Heap이란?
우선순위 큐를 구현하기 위한 가장 적절한 자료구조임
이진 트리 형태를 가지며 우선순위가 높은 요소가 먼저 나가기 위해 요소가 삽입, 삭제 될 때 바로 정렬됨
특징
우선순위가 높은 요소가 먼저 나가는 특징을 가짐
루트가 가장 큰 값이 되는 최대 힙과 루트가 가장 작은 값이 되는 최소 힙이 있음
추가
요소가 추가될 때는 트리의 가장 마지막에 정점이 위치함
추가 후 부모 정점보다 우선순위가 높으면 부모 정점과 순서를 바꿈
이 과정 반복 -> 우선순위 가장 높은 정점이 루트가 됨
시간복잡도 : O(logN) 완전이진트리 높이: logN
제거
요소 제거는 루트 정점만 가능함
루트 정점이 제거된 후 마지막 정점이 루트에 위치함
힙에 대해서 설명해보세요.
완전 이진 트리의 일종으로 반정렬 상태를 유지하여 최대 혹은 최소의 값을 빠르게 반환할 수 있는 자료구조임. 주로 우선순위 큐를 구현하기 위해 사용됨
힙을 배열로 구현한다고 하면, 어떻게 값을 저장할 수 있을까요?
루트 노드를 첫번째 인덱스에 저장하고 부모 노드의 인덱스를 기준으로 2i에 왼쪽 자식 2i+1에 오른쪽 자식을 저장
힙의 삽입, 삭제 방식에 대해 설명하고, 왜 이진탐색트리와 달리 편향이 발생하지 않는지 설명해 주세요.
삽입은 맨 마지막 자리에 요소를 삽입 후 힙의 속성에 맞을 때까지 부모,자식간의 교환을 진행함. 삭제는 루트와 마지막 요소를 스왑한 후 마지막 요소를 반환함. 그 후 힙의 속성에 맞을 때까지 또 부모,자식간의 교환을 진행함.
이진 탐색 트리에 데이터를 정렬된 순서로 삽입하는 경우, 트리가 한 쪽으로 치우칠 가능성이 큼. 예를 들어, 작은 값부터 큰 값으로 순차적으로 삽입하면, 트리는 거의 연결 리스트 형태가 되어버림. 반면 힙에서는 데이터를 삽입 및 삭제할 때 특별한 규칙을 따라서 트리를 조정하기 때문에 편향이 발생하지 않음.
힙 정렬의 시간복잡도는 어떻게 되나요? Stable 한가요?
데이터를 힙으로 구성하는데 O(n)이 소요되고, 힙을 재조정하는 작업을 반복해야해서 O(nlogn)시간이 소요됨
stable한지 안한지는 동일한 값들의 상대적인 순서가 정렬 전후에도 유지되냐안되냐를 말하는데, 힙정렬은 보다시피 원래 배열의순서를 무시하고 힙을 구성하기 때문에 , Stable하다고 할 수 없음
🫠
출처 : https://velog.io/@dbghwns11/CS-%EC%A0%95%EB%A6%AC-2
https://alreadyusedadress.tistory.com/326
