목록heap (1)

PSD( Private-Self-Development )

힙(heap)

힙 이란? 완전 이진트리의 일종이며, 우선순위 큐를 위해 만들어진 자료구조이다. 우선순위 큐? 우선순위 개념을 큐에 적용한 자료 구조이다. 가장 우선순위가 높은 데이터가 먼저 나간다. 배열, 연결 리스트, 힙으로 구현 가능하다. 이중 힙으로 구현하는 것이 가장 성능이 좋다. 힙 특징 힙은 일종의 반정렬 상태를 유지한다.( 큰 값이 위에 있으면 작은 값은 아래에 있다는 정도 ) 부모 노드의 값이 자식 노드보다 항상 크거나 작은 이진트리이다. 중복을 허용한다. 최대값, 최소값을 조회하기 좋다 힙 종류 최대 힙 부모 노드가 자식 노드보다 크거나 같은 완전 이진트리 최소 힙 부모 노드가 자식 노드보다 작거나 같은 완전 이진트리 힙 구현 힙을 저장하는 표준 자료구조는 배열이다. 배열의 첫 번째 인덱스인 0은 사용..
Backend/자료구조 2022. 12. 20. 16:23
이전 Prev 1 Next 다음