[자료구조] 우선순위 큐(priority queue), 힙(heap)

2021. 7. 17. 22:54

공부했던 자료 정리하는 용도입니다.

재배포, 수정하지 마세요.

우선순위 큐(priority queue)

큐에 우선순위의 개념을 도입한 자료구조
데이터들은 우선순위를 가지고 있고, 우선순위가 높은 데이터가 먼저 나가게 된다.
우선순위에 따라 스택이나 큐처럼 동작하기도 한다.

우선순위 큐 연산

객체 : n개의 element형의 우선 순위를 가진 요소들의 모임
연산 :
    create() ::= 우선순위 큐 생성
    init(q) ::= 우선순위 큐 q를 초기화
    is_empty(q) ::= 우선순위 큐 q가 비어있는지 검사
    is_full(q) ::= 우선순위 큐 q가 포화상태인지 검사
    insert(q, x) ::= 우선순위 큐 q에 요소 x를 추가
    delete(q) ::= 우선순위 큐로부터 가장 우선순위가 높은 요소를 삭제하고 해당 요소 반환
    find(q) ::= 우선순위가 가장 높은 요소를 반환

우선순위 큐 구현 방법

배열을 이용
- 정렬된 배열을 사용하는 경우
- 정렬되지 X 배열을 사용하는 경우
연결 리스트를 이용
- 정렬된 연결 리스트를 사용하는 경우
- 정렬되지 않은 연결 리스트를 사용하는 경우
힙(heap)을 이용

각 구현 방법에 따른 시간 복잡도

자료 구조	삽입 연산	삭제 연산
정렬된 배열 이용	$O(n)$	$O(1)$
정렬되지 않은 배열 이용	$O(1)$	$O(n)$ 우선순위가 높은 요소를 찾아야하기 때문
정렬된 연결 리스트를 이용	$O(n)$ 우선순위가 높은 요소를 찾아야 하기 때문	$O(1)$
정렬되지 않은 연결리스트 이용	$O(1)$ (처음에 삽입하는 경우)	$O(n)$ 배열과 마찬가지로 우선순위가 높은 요소를 찾아야 하기 때문
힙(heap)을 이용	$O(log_2n)$	$O(log_2n)$

힙(heap)

완전 이진트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다.
이진 탐색 트리와 달리 중복 값을 허용한다.
부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 이진트리이다.
일종의 느슨한 정렬 상태를 유지한다. (삭제 연산이 수행될 때 최대값(root)만 찾으면 되므로 전체를 정렬하지 않는다.)
최대값이나 최소값을 빠르게 찾을 때 유리하다.

힙의 종류

최대 힙(max heap)
: 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진트리
최소 힙(min heap)
: 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진트리

힙 구현 방법

배열을 이용한 구현
- 정렬된 배열 이용
- 정렬되지 X 배열 이용
- 구현을 쉽게 하기 위해서 인덱스 0은 사용하지 않는다.
- 연산을 통해 노드의 인덱스를 알 수 있다.
왼쪽 자식의 인덱스 = (부모의 인덱스) * 2
오른쪽 자식의 인덱스 = (부모의 인덱스) * 2 + 1
부모의 인덱스 = (자식의 인덱스) / 2
연결 리스트 이용

힙의 시간 복잡도

삽입 연산 : $O(log_2n)$
삭제 연산 : $O(log_2n)$

힙의 연산

삽입 연산
(1) 요소를 힙의 가장 마지막 노드로 삽입
(2) 부모 노드와 비교하여 부모 노드보다 클 경우 값 교환(부모 노드보다 작을 때까지 반복)
삭제 연산
(1) 루트 노드 삭제
(2) 빈 루트 자리에 힙의 마지막 노드를 가져옴
(3) 양쪽 자식 중 큰 값과 교환이 일어남(자식 노드보다 클 때까지 반복)

힙 정렬(heap sort)

최대 힙을 이용하면 정렬을 할 수 있다. 데이터를 차례대로 최대 힙에 추가하여 힙을 생성한 뒤, 요소를 하나씩 빼서 뒤쪽부터 저장하면 오름차순이 된다. 이렇게 힙을 사용하는 정렬 알고리즘을 힙 정렬(heap sort)이라고 한다. 전체 자료를 정렬하지 않고 큰 값만 필요한 경우에도 유용하게 사용된다.

시간 복잡도 : $O(nlog_2n)$ (전체 높이가 $log_2n$ 인 완전 이진트리이기 때문)

힙 응용

LPT 알고리즘(longest processing time first) : 가장 긴 작업을 우선적으로 할당하는 것
허프만 코드(Huffman codes)
ex) 영문자 빈도수를 이용한 데이터 압축

저작자표시 비영리 변경금지

'기타 > 자료구조' 카테고리의 다른 글

[자료구조] 그래프(graph) (0)	2021.07.31
[자료구조] 트리, 이진 트리, 이진 탐색 트리 (0)	2021.06.18
[자료구조] 큐(Queue), 덱(Deque) (0)	2021.02.02
[자료구조] 스택(Stack) (0)	2021.01.26
순환 알고리즘 (0)	2021.01.25

공부했던 자료 정리하는 용도입니다.

재배포, 수정하지 마세요.

우선순위 큐(priority queue)

큐에 우선순위의 개념을 도입한 자료구조
데이터들은 우선순위를 가지고 있고, 우선순위가 높은 데이터가 먼저 나가게 된다.
우선순위에 따라 스택이나 큐처럼 동작하기도 한다.

우선순위 큐 연산

객체 : n개의 element형의 우선 순위를 가진 요소들의 모임
연산 :
    create() ::= 우선순위 큐 생성
    init(q) ::= 우선순위 큐 q를 초기화
    is_empty(q) ::= 우선순위 큐 q가 비어있는지 검사
    is_full(q) ::= 우선순위 큐 q가 포화상태인지 검사
    insert(q, x) ::= 우선순위 큐 q에 요소 x를 추가
    delete(q) ::= 우선순위 큐로부터 가장 우선순위가 높은 요소를 삭제하고 해당 요소 반환
    find(q) ::= 우선순위가 가장 높은 요소를 반환

우선순위 큐 구현 방법

배열을 이용
- 정렬된 배열을 사용하는 경우
- 정렬되지 X 배열을 사용하는 경우
연결 리스트를 이용
- 정렬된 연결 리스트를 사용하는 경우
- 정렬되지 않은 연결 리스트를 사용하는 경우
힙(heap)을 이용

각 구현 방법에 따른 시간 복잡도

자료 구조	삽입 연산	삭제 연산
정렬된 배열 이용	$O(n)$	$O(1)$
정렬되지 않은 배열 이용	$O(1)$	$O(n)$ 우선순위가 높은 요소를 찾아야하기 때문
정렬된 연결 리스트를 이용	$O(n)$ 우선순위가 높은 요소를 찾아야 하기 때문	$O(1)$
정렬되지 않은 연결리스트 이용	$O(1)$ (처음에 삽입하는 경우)	$O(n)$ 배열과 마찬가지로 우선순위가 높은 요소를 찾아야 하기 때문
힙(heap)을 이용	$O(log_2n)$	$O(log_2n)$

힙(heap)

완전 이진트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다.
이진 탐색 트리와 달리 중복 값을 허용한다.
부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 이진트리이다.
일종의 느슨한 정렬 상태를 유지한다. (삭제 연산이 수행될 때 최대값(root)만 찾으면 되므로 전체를 정렬하지 않는다.)
최대값이나 최소값을 빠르게 찾을 때 유리하다.

힙의 종류

최대 힙(max heap)
: 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진트리
최소 힙(min heap)
: 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진트리

힙 구현 방법

배열을 이용한 구현
- 정렬된 배열 이용
- 정렬되지 X 배열 이용
- 구현을 쉽게 하기 위해서 인덱스 0은 사용하지 않는다.
- 연산을 통해 노드의 인덱스를 알 수 있다.
왼쪽 자식의 인덱스 = (부모의 인덱스) * 2
오른쪽 자식의 인덱스 = (부모의 인덱스) * 2 + 1
부모의 인덱스 = (자식의 인덱스) / 2
연결 리스트 이용

힙의 시간 복잡도

삽입 연산 : $O(log_2n)$
삭제 연산 : $O(log_2n)$

힙의 연산

삽입 연산
(1) 요소를 힙의 가장 마지막 노드로 삽입
(2) 부모 노드와 비교하여 부모 노드보다 클 경우 값 교환(부모 노드보다 작을 때까지 반복)
삭제 연산
(1) 루트 노드 삭제
(2) 빈 루트 자리에 힙의 마지막 노드를 가져옴
(3) 양쪽 자식 중 큰 값과 교환이 일어남(자식 노드보다 클 때까지 반복)

힙 정렬(heap sort)

시간 복잡도 : $O(nlog_2n)$ (전체 높이가 $log_2n$ 인 완전 이진트리이기 때문)

힙 응용

LPT 알고리즘(longest processing time first) : 가장 긴 작업을 우선적으로 할당하는 것
허프만 코드(Huffman codes)
ex) 영문자 빈도수를 이용한 데이터 압축

저작자표시 비영리 변경금지

'기타 > 자료구조' 카테고리의 다른 글

[자료구조] 그래프(graph) (0)	2021.07.31
[자료구조] 트리, 이진 트리, 이진 탐색 트리 (0)	2021.06.18
[자료구조] 큐(Queue), 덱(Deque) (0)	2021.02.02
[자료구조] 스택(Stack) (0)	2021.01.26
순환 알고리즘 (0)	2021.01.25

공부했던 자료 정리하는 용도입니다.

재배포, 수정하지 마세요.

우선순위 큐(priority queue)

큐에 우선순위의 개념을 도입한 자료구조
데이터들은 우선순위를 가지고 있고, 우선순위가 높은 데이터가 먼저 나가게 된다.
우선순위에 따라 스택이나 큐처럼 동작하기도 한다.

우선순위 큐 연산

객체 : n개의 element형의 우선 순위를 가진 요소들의 모임
연산 :
    create() ::= 우선순위 큐 생성
    init(q) ::= 우선순위 큐 q를 초기화
    is_empty(q) ::= 우선순위 큐 q가 비어있는지 검사
    is_full(q) ::= 우선순위 큐 q가 포화상태인지 검사
    insert(q, x) ::= 우선순위 큐 q에 요소 x를 추가
    delete(q) ::= 우선순위 큐로부터 가장 우선순위가 높은 요소를 삭제하고 해당 요소 반환
    find(q) ::= 우선순위가 가장 높은 요소를 반환

우선순위 큐 구현 방법

배열을 이용
- 정렬된 배열을 사용하는 경우
- 정렬되지 X 배열을 사용하는 경우
연결 리스트를 이용
- 정렬된 연결 리스트를 사용하는 경우
- 정렬되지 않은 연결 리스트를 사용하는 경우
힙(heap)을 이용

각 구현 방법에 따른 시간 복잡도

자료 구조	삽입 연산	삭제 연산
정렬된 배열 이용	$O(n)$	$O(1)$
정렬되지 않은 배열 이용	$O(1)$	$O(n)$ 우선순위가 높은 요소를 찾아야하기 때문
정렬된 연결 리스트를 이용	$O(n)$ 우선순위가 높은 요소를 찾아야 하기 때문	$O(1)$
정렬되지 않은 연결리스트 이용	$O(1)$ (처음에 삽입하는 경우)	$O(n)$ 배열과 마찬가지로 우선순위가 높은 요소를 찾아야 하기 때문
힙(heap)을 이용	$O(log_2n)$	$O(log_2n)$

힙(heap)

완전 이진트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다.
이진 탐색 트리와 달리 중복 값을 허용한다.
부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 이진트리이다.
일종의 느슨한 정렬 상태를 유지한다. (삭제 연산이 수행될 때 최대값(root)만 찾으면 되므로 전체를 정렬하지 않는다.)
최대값이나 최소값을 빠르게 찾을 때 유리하다.

힙의 종류

최대 힙(max heap)
: 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진트리
최소 힙(min heap)
: 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진트리

힙 구현 방법

배열을 이용한 구현
- 정렬된 배열 이용
- 정렬되지 X 배열 이용
- 구현을 쉽게 하기 위해서 인덱스 0은 사용하지 않는다.
- 연산을 통해 노드의 인덱스를 알 수 있다.
왼쪽 자식의 인덱스 = (부모의 인덱스) * 2
오른쪽 자식의 인덱스 = (부모의 인덱스) * 2 + 1
부모의 인덱스 = (자식의 인덱스) / 2
연결 리스트 이용

힙의 시간 복잡도

삽입 연산 : $O(log_2n)$
삭제 연산 : $O(log_2n)$

힙의 연산

삽입 연산
(1) 요소를 힙의 가장 마지막 노드로 삽입
(2) 부모 노드와 비교하여 부모 노드보다 클 경우 값 교환(부모 노드보다 작을 때까지 반복)
삭제 연산
(1) 루트 노드 삭제
(2) 빈 루트 자리에 힙의 마지막 노드를 가져옴
(3) 양쪽 자식 중 큰 값과 교환이 일어남(자식 노드보다 클 때까지 반복)

힙 정렬(heap sort)

시간 복잡도 : $O(nlog_2n)$ (전체 높이가 $log_2n$ 인 완전 이진트리이기 때문)

힙 응용

LPT 알고리즘(longest processing time first) : 가장 긴 작업을 우선적으로 할당하는 것
허프만 코드(Huffman codes)
ex) 영문자 빈도수를 이용한 데이터 압축

저작자표시 비영리 변경금지

'기타 > 자료구조' 카테고리의 다른 글

[자료구조] 그래프(graph) (0)	2021.07.31
[자료구조] 트리, 이진 트리, 이진 탐색 트리 (0)	2021.06.18
[자료구조] 큐(Queue), 덱(Deque) (0)	2021.02.02
[자료구조] 스택(Stack) (0)	2021.01.26
순환 알고리즘 (0)	2021.01.25

공부했던 자료 정리하는 용도입니다.

재배포, 수정하지 마세요.

우선순위 큐(priority queue)

큐에 우선순위의 개념을 도입한 자료구조
데이터들은 우선순위를 가지고 있고, 우선순위가 높은 데이터가 먼저 나가게 된다.
우선순위에 따라 스택이나 큐처럼 동작하기도 한다.

우선순위 큐 연산

객체 : n개의 element형의 우선 순위를 가진 요소들의 모임
연산 :
    create() ::= 우선순위 큐 생성
    init(q) ::= 우선순위 큐 q를 초기화
    is_empty(q) ::= 우선순위 큐 q가 비어있는지 검사
    is_full(q) ::= 우선순위 큐 q가 포화상태인지 검사
    insert(q, x) ::= 우선순위 큐 q에 요소 x를 추가
    delete(q) ::= 우선순위 큐로부터 가장 우선순위가 높은 요소를 삭제하고 해당 요소 반환
    find(q) ::= 우선순위가 가장 높은 요소를 반환

우선순위 큐 구현 방법

배열을 이용
- 정렬된 배열을 사용하는 경우
- 정렬되지 X 배열을 사용하는 경우
연결 리스트를 이용
- 정렬된 연결 리스트를 사용하는 경우
- 정렬되지 않은 연결 리스트를 사용하는 경우
힙(heap)을 이용

각 구현 방법에 따른 시간 복잡도

자료 구조	삽입 연산	삭제 연산
정렬된 배열 이용	$O(n)$	$O(1)$
정렬되지 않은 배열 이용	$O(1)$	$O(n)$ 우선순위가 높은 요소를 찾아야하기 때문
정렬된 연결 리스트를 이용	$O(n)$ 우선순위가 높은 요소를 찾아야 하기 때문	$O(1)$
정렬되지 않은 연결리스트 이용	$O(1)$ (처음에 삽입하는 경우)	$O(n)$ 배열과 마찬가지로 우선순위가 높은 요소를 찾아야 하기 때문
힙(heap)을 이용	$O(log_2n)$	$O(log_2n)$

힙(heap)

완전 이진트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다.
이진 탐색 트리와 달리 중복 값을 허용한다.
부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 이진트리이다.
일종의 느슨한 정렬 상태를 유지한다. (삭제 연산이 수행될 때 최대값(root)만 찾으면 되므로 전체를 정렬하지 않는다.)
최대값이나 최소값을 빠르게 찾을 때 유리하다.

힙의 종류

최대 힙(max heap)
: 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진트리
최소 힙(min heap)
: 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진트리

힙 구현 방법

배열을 이용한 구현
- 정렬된 배열 이용
- 정렬되지 X 배열 이용
- 구현을 쉽게 하기 위해서 인덱스 0은 사용하지 않는다.
- 연산을 통해 노드의 인덱스를 알 수 있다.
왼쪽 자식의 인덱스 = (부모의 인덱스) * 2
오른쪽 자식의 인덱스 = (부모의 인덱스) * 2 + 1
부모의 인덱스 = (자식의 인덱스) / 2
연결 리스트 이용

힙의 시간 복잡도

삽입 연산 : $O(log_2n)$
삭제 연산 : $O(log_2n)$

힙의 연산

삽입 연산
(1) 요소를 힙의 가장 마지막 노드로 삽입
(2) 부모 노드와 비교하여 부모 노드보다 클 경우 값 교환(부모 노드보다 작을 때까지 반복)
삭제 연산
(1) 루트 노드 삭제
(2) 빈 루트 자리에 힙의 마지막 노드를 가져옴
(3) 양쪽 자식 중 큰 값과 교환이 일어남(자식 노드보다 클 때까지 반복)

힙 정렬(heap sort)

시간 복잡도 : $O(nlog_2n)$ (전체 높이가 $log_2n$ 인 완전 이진트리이기 때문)

힙 응용

LPT 알고리즘(longest processing time first) : 가장 긴 작업을 우선적으로 할당하는 것
허프만 코드(Huffman codes)
ex) 영문자 빈도수를 이용한 데이터 압축

저작자표시 비영리 변경금지

'기타 > 자료구조' 카테고리의 다른 글

[자료구조] 그래프(graph) (0)	2021.07.31
[자료구조] 트리, 이진 트리, 이진 탐색 트리 (0)	2021.06.18
[자료구조] 큐(Queue), 덱(Deque) (0)	2021.02.02
[자료구조] 스택(Stack) (0)	2021.01.26
순환 알고리즘 (0)	2021.01.25

공부했던 자료 정리하는 용도입니다.

재배포, 수정하지 마세요.

우선순위 큐(priority queue)

큐에 우선순위의 개념을 도입한 자료구조
데이터들은 우선순위를 가지고 있고, 우선순위가 높은 데이터가 먼저 나가게 된다.
우선순위에 따라 스택이나 큐처럼 동작하기도 한다.

우선순위 큐 연산

객체 : n개의 element형의 우선 순위를 가진 요소들의 모임
연산 :
    create() ::= 우선순위 큐 생성
    init(q) ::= 우선순위 큐 q를 초기화
    is_empty(q) ::= 우선순위 큐 q가 비어있는지 검사
    is_full(q) ::= 우선순위 큐 q가 포화상태인지 검사
    insert(q, x) ::= 우선순위 큐 q에 요소 x를 추가
    delete(q) ::= 우선순위 큐로부터 가장 우선순위가 높은 요소를 삭제하고 해당 요소 반환
    find(q) ::= 우선순위가 가장 높은 요소를 반환

우선순위 큐 구현 방법

배열을 이용
- 정렬된 배열을 사용하는 경우
- 정렬되지 X 배열을 사용하는 경우
연결 리스트를 이용
- 정렬된 연결 리스트를 사용하는 경우
- 정렬되지 않은 연결 리스트를 사용하는 경우
힙(heap)을 이용

각 구현 방법에 따른 시간 복잡도

자료 구조	삽입 연산	삭제 연산
정렬된 배열 이용	$O(n)$	$O(1)$
정렬되지 않은 배열 이용	$O(1)$	$O(n)$ 우선순위가 높은 요소를 찾아야하기 때문
정렬된 연결 리스트를 이용	$O(n)$ 우선순위가 높은 요소를 찾아야 하기 때문	$O(1)$
정렬되지 않은 연결리스트 이용	$O(1)$ (처음에 삽입하는 경우)	$O(n)$ 배열과 마찬가지로 우선순위가 높은 요소를 찾아야 하기 때문
힙(heap)을 이용	$O(log_2n)$	$O(log_2n)$

힙(heap)

완전 이진트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다.
이진 탐색 트리와 달리 중복 값을 허용한다.
부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 이진트리이다.
일종의 느슨한 정렬 상태를 유지한다. (삭제 연산이 수행될 때 최대값(root)만 찾으면 되므로 전체를 정렬하지 않는다.)
최대값이나 최소값을 빠르게 찾을 때 유리하다.

힙의 종류

최대 힙(max heap)
: 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진트리
최소 힙(min heap)
: 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진트리

힙 구현 방법

배열을 이용한 구현
- 정렬된 배열 이용
- 정렬되지 X 배열 이용
- 구현을 쉽게 하기 위해서 인덱스 0은 사용하지 않는다.
- 연산을 통해 노드의 인덱스를 알 수 있다.
왼쪽 자식의 인덱스 = (부모의 인덱스) * 2
오른쪽 자식의 인덱스 = (부모의 인덱스) * 2 + 1
부모의 인덱스 = (자식의 인덱스) / 2
연결 리스트 이용

힙의 시간 복잡도

삽입 연산 : $O(log_2n)$
삭제 연산 : $O(log_2n)$

힙의 연산

삽입 연산
(1) 요소를 힙의 가장 마지막 노드로 삽입
(2) 부모 노드와 비교하여 부모 노드보다 클 경우 값 교환(부모 노드보다 작을 때까지 반복)
삭제 연산
(1) 루트 노드 삭제
(2) 빈 루트 자리에 힙의 마지막 노드를 가져옴
(3) 양쪽 자식 중 큰 값과 교환이 일어남(자식 노드보다 클 때까지 반복)

힙 정렬(heap sort)

시간 복잡도 : $O(nlog_2n)$ (전체 높이가 $log_2n$ 인 완전 이진트리이기 때문)

힙 응용

LPT 알고리즘(longest processing time first) : 가장 긴 작업을 우선적으로 할당하는 것
허프만 코드(Huffman codes)
ex) 영문자 빈도수를 이용한 데이터 압축

저작자표시 비영리 변경금지

'기타 > 자료구조' 카테고리의 다른 글

[자료구조] 그래프(graph) (0)	2021.07.31
[자료구조] 트리, 이진 트리, 이진 탐색 트리 (0)	2021.06.18
[자료구조] 큐(Queue), 덱(Deque) (0)	2021.02.02
[자료구조] 스택(Stack) (0)	2021.01.26
순환 알고리즘 (0)	2021.01.25

공부했던 자료 정리하는 용도입니다.

재배포, 수정하지 마세요.

우선순위 큐(priority queue)

큐에 우선순위의 개념을 도입한 자료구조
데이터들은 우선순위를 가지고 있고, 우선순위가 높은 데이터가 먼저 나가게 된다.
우선순위에 따라 스택이나 큐처럼 동작하기도 한다.

우선순위 큐 연산

객체 : n개의 element형의 우선 순위를 가진 요소들의 모임
연산 :
    create() ::= 우선순위 큐 생성
    init(q) ::= 우선순위 큐 q를 초기화
    is_empty(q) ::= 우선순위 큐 q가 비어있는지 검사
    is_full(q) ::= 우선순위 큐 q가 포화상태인지 검사
    insert(q, x) ::= 우선순위 큐 q에 요소 x를 추가
    delete(q) ::= 우선순위 큐로부터 가장 우선순위가 높은 요소를 삭제하고 해당 요소 반환
    find(q) ::= 우선순위가 가장 높은 요소를 반환

우선순위 큐 구현 방법

배열을 이용
- 정렬된 배열을 사용하는 경우
- 정렬되지 X 배열을 사용하는 경우
연결 리스트를 이용
- 정렬된 연결 리스트를 사용하는 경우
- 정렬되지 않은 연결 리스트를 사용하는 경우
힙(heap)을 이용

각 구현 방법에 따른 시간 복잡도

자료 구조	삽입 연산	삭제 연산
정렬된 배열 이용	$O(n)$	$O(1)$
정렬되지 않은 배열 이용	$O(1)$	$O(n)$ 우선순위가 높은 요소를 찾아야하기 때문
정렬된 연결 리스트를 이용	$O(n)$ 우선순위가 높은 요소를 찾아야 하기 때문	$O(1)$
정렬되지 않은 연결리스트 이용	$O(1)$ (처음에 삽입하는 경우)	$O(n)$ 배열과 마찬가지로 우선순위가 높은 요소를 찾아야 하기 때문
힙(heap)을 이용	$O(log_2n)$	$O(log_2n)$

힙(heap)

완전 이진트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다.
이진 탐색 트리와 달리 중복 값을 허용한다.
부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 이진트리이다.
일종의 느슨한 정렬 상태를 유지한다. (삭제 연산이 수행될 때 최대값(root)만 찾으면 되므로 전체를 정렬하지 않는다.)
최대값이나 최소값을 빠르게 찾을 때 유리하다.

힙의 종류

최대 힙(max heap)
: 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진트리
최소 힙(min heap)
: 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진트리

힙 구현 방법

배열을 이용한 구현
- 정렬된 배열 이용
- 정렬되지 X 배열 이용
- 구현을 쉽게 하기 위해서 인덱스 0은 사용하지 않는다.
- 연산을 통해 노드의 인덱스를 알 수 있다.
왼쪽 자식의 인덱스 = (부모의 인덱스) * 2
오른쪽 자식의 인덱스 = (부모의 인덱스) * 2 + 1
부모의 인덱스 = (자식의 인덱스) / 2
연결 리스트 이용

힙의 시간 복잡도

삽입 연산 : $O(log_2n)$
삭제 연산 : $O(log_2n)$

힙의 연산

삽입 연산
(1) 요소를 힙의 가장 마지막 노드로 삽입
(2) 부모 노드와 비교하여 부모 노드보다 클 경우 값 교환(부모 노드보다 작을 때까지 반복)
삭제 연산
(1) 루트 노드 삭제
(2) 빈 루트 자리에 힙의 마지막 노드를 가져옴
(3) 양쪽 자식 중 큰 값과 교환이 일어남(자식 노드보다 클 때까지 반복)

힙 정렬(heap sort)

시간 복잡도 : $O(nlog_2n)$ (전체 높이가 $log_2n$ 인 완전 이진트리이기 때문)

힙 응용

LPT 알고리즘(longest processing time first) : 가장 긴 작업을 우선적으로 할당하는 것
허프만 코드(Huffman codes)
ex) 영문자 빈도수를 이용한 데이터 압축

저작자표시 비영리 변경금지

'기타 > 자료구조' 카테고리의 다른 글

[자료구조] 그래프(graph) (0)	2021.07.31
[자료구조] 트리, 이진 트리, 이진 탐색 트리 (0)	2021.06.18
[자료구조] 큐(Queue), 덱(Deque) (0)	2021.02.02
[자료구조] 스택(Stack) (0)	2021.01.26
순환 알고리즘 (0)	2021.01.25

공부했던 자료 정리하는 용도입니다.

재배포, 수정하지 마세요.

우선순위 큐(priority queue)

큐에 우선순위의 개념을 도입한 자료구조
데이터들은 우선순위를 가지고 있고, 우선순위가 높은 데이터가 먼저 나가게 된다.
우선순위에 따라 스택이나 큐처럼 동작하기도 한다.

우선순위 큐 연산

객체 : n개의 element형의 우선 순위를 가진 요소들의 모임
연산 :
    create() ::= 우선순위 큐 생성
    init(q) ::= 우선순위 큐 q를 초기화
    is_empty(q) ::= 우선순위 큐 q가 비어있는지 검사
    is_full(q) ::= 우선순위 큐 q가 포화상태인지 검사
    insert(q, x) ::= 우선순위 큐 q에 요소 x를 추가
    delete(q) ::= 우선순위 큐로부터 가장 우선순위가 높은 요소를 삭제하고 해당 요소 반환
    find(q) ::= 우선순위가 가장 높은 요소를 반환

우선순위 큐 구현 방법

배열을 이용
- 정렬된 배열을 사용하는 경우
- 정렬되지 X 배열을 사용하는 경우
연결 리스트를 이용
- 정렬된 연결 리스트를 사용하는 경우
- 정렬되지 않은 연결 리스트를 사용하는 경우
힙(heap)을 이용

각 구현 방법에 따른 시간 복잡도

자료 구조	삽입 연산	삭제 연산
정렬된 배열 이용	$O(n)$	$O(1)$
정렬되지 않은 배열 이용	$O(1)$	$O(n)$ 우선순위가 높은 요소를 찾아야하기 때문
정렬된 연결 리스트를 이용	$O(n)$ 우선순위가 높은 요소를 찾아야 하기 때문	$O(1)$
정렬되지 않은 연결리스트 이용	$O(1)$ (처음에 삽입하는 경우)	$O(n)$ 배열과 마찬가지로 우선순위가 높은 요소를 찾아야 하기 때문
힙(heap)을 이용	$O(log_2n)$	$O(log_2n)$

힙(heap)

완전 이진트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다.
이진 탐색 트리와 달리 중복 값을 허용한다.
부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 이진트리이다.
일종의 느슨한 정렬 상태를 유지한다. (삭제 연산이 수행될 때 최대값(root)만 찾으면 되므로 전체를 정렬하지 않는다.)
최대값이나 최소값을 빠르게 찾을 때 유리하다.

힙의 종류

최대 힙(max heap)
: 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진트리
최소 힙(min heap)
: 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진트리

힙 구현 방법

배열을 이용한 구현
- 정렬된 배열 이용
- 정렬되지 X 배열 이용
- 구현을 쉽게 하기 위해서 인덱스 0은 사용하지 않는다.
- 연산을 통해 노드의 인덱스를 알 수 있다.
왼쪽 자식의 인덱스 = (부모의 인덱스) * 2
오른쪽 자식의 인덱스 = (부모의 인덱스) * 2 + 1
부모의 인덱스 = (자식의 인덱스) / 2
연결 리스트 이용

힙의 시간 복잡도

삽입 연산 : $O(log_2n)$
삭제 연산 : $O(log_2n)$

힙의 연산

삽입 연산
(1) 요소를 힙의 가장 마지막 노드로 삽입
(2) 부모 노드와 비교하여 부모 노드보다 클 경우 값 교환(부모 노드보다 작을 때까지 반복)
삭제 연산
(1) 루트 노드 삭제
(2) 빈 루트 자리에 힙의 마지막 노드를 가져옴
(3) 양쪽 자식 중 큰 값과 교환이 일어남(자식 노드보다 클 때까지 반복)

힙 정렬(heap sort)

시간 복잡도 : $O(nlog_2n)$ (전체 높이가 $log_2n$ 인 완전 이진트리이기 때문)

힙 응용

LPT 알고리즘(longest processing time first) : 가장 긴 작업을 우선적으로 할당하는 것
허프만 코드(Huffman codes)
ex) 영문자 빈도수를 이용한 데이터 압축

저작자표시 비영리 변경금지

'기타 > 자료구조' 카테고리의 다른 글

[자료구조] 그래프(graph) (0)	2021.07.31
[자료구조] 트리, 이진 트리, 이진 탐색 트리 (0)	2021.06.18
[자료구조] 큐(Queue), 덱(Deque) (0)	2021.02.02
[자료구조] 스택(Stack) (0)	2021.01.26
순환 알고리즘 (0)	2021.01.25

공부했던 자료 정리하는 용도입니다.

재배포, 수정하지 마세요.

우선순위 큐(priority queue)

큐에 우선순위의 개념을 도입한 자료구조
데이터들은 우선순위를 가지고 있고, 우선순위가 높은 데이터가 먼저 나가게 된다.
우선순위에 따라 스택이나 큐처럼 동작하기도 한다.

우선순위 큐 연산

객체 : n개의 element형의 우선 순위를 가진 요소들의 모임
연산 :
    create() ::= 우선순위 큐 생성
    init(q) ::= 우선순위 큐 q를 초기화
    is_empty(q) ::= 우선순위 큐 q가 비어있는지 검사
    is_full(q) ::= 우선순위 큐 q가 포화상태인지 검사
    insert(q, x) ::= 우선순위 큐 q에 요소 x를 추가
    delete(q) ::= 우선순위 큐로부터 가장 우선순위가 높은 요소를 삭제하고 해당 요소 반환
    find(q) ::= 우선순위가 가장 높은 요소를 반환

우선순위 큐 구현 방법

배열을 이용
- 정렬된 배열을 사용하는 경우
- 정렬되지 X 배열을 사용하는 경우
연결 리스트를 이용
- 정렬된 연결 리스트를 사용하는 경우
- 정렬되지 않은 연결 리스트를 사용하는 경우
힙(heap)을 이용

각 구현 방법에 따른 시간 복잡도

자료 구조	삽입 연산	삭제 연산
정렬된 배열 이용	$O(n)$	$O(1)$
정렬되지 않은 배열 이용	$O(1)$	$O(n)$ 우선순위가 높은 요소를 찾아야하기 때문
정렬된 연결 리스트를 이용	$O(n)$ 우선순위가 높은 요소를 찾아야 하기 때문	$O(1)$
정렬되지 않은 연결리스트 이용	$O(1)$ (처음에 삽입하는 경우)	$O(n)$ 배열과 마찬가지로 우선순위가 높은 요소를 찾아야 하기 때문
힙(heap)을 이용	$O(log_2n)$	$O(log_2n)$

힙(heap)

완전 이진트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다.
이진 탐색 트리와 달리 중복 값을 허용한다.
부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 이진트리이다.
일종의 느슨한 정렬 상태를 유지한다. (삭제 연산이 수행될 때 최대값(root)만 찾으면 되므로 전체를 정렬하지 않는다.)
최대값이나 최소값을 빠르게 찾을 때 유리하다.

힙의 종류

최대 힙(max heap)
: 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진트리
최소 힙(min heap)
: 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진트리

힙 구현 방법

배열을 이용한 구현
- 정렬된 배열 이용
- 정렬되지 X 배열 이용
- 구현을 쉽게 하기 위해서 인덱스 0은 사용하지 않는다.
- 연산을 통해 노드의 인덱스를 알 수 있다.
왼쪽 자식의 인덱스 = (부모의 인덱스) * 2
오른쪽 자식의 인덱스 = (부모의 인덱스) * 2 + 1
부모의 인덱스 = (자식의 인덱스) / 2
연결 리스트 이용

힙의 시간 복잡도

삽입 연산 : $O(log_2n)$
삭제 연산 : $O(log_2n)$

힙의 연산

삽입 연산
(1) 요소를 힙의 가장 마지막 노드로 삽입
(2) 부모 노드와 비교하여 부모 노드보다 클 경우 값 교환(부모 노드보다 작을 때까지 반복)
삭제 연산
(1) 루트 노드 삭제
(2) 빈 루트 자리에 힙의 마지막 노드를 가져옴
(3) 양쪽 자식 중 큰 값과 교환이 일어남(자식 노드보다 클 때까지 반복)

힙 정렬(heap sort)

시간 복잡도 : $O(nlog_2n)$ (전체 높이가 $log_2n$ 인 완전 이진트리이기 때문)

힙 응용

LPT 알고리즘(longest processing time first) : 가장 긴 작업을 우선적으로 할당하는 것
허프만 코드(Huffman codes)
ex) 영문자 빈도수를 이용한 데이터 압축

저작자표시 비영리 변경금지

'기타 > 자료구조' 카테고리의 다른 글

[자료구조] 그래프(graph) (0)	2021.07.31
[자료구조] 트리, 이진 트리, 이진 탐색 트리 (0)	2021.06.18
[자료구조] 큐(Queue), 덱(Deque) (0)	2021.02.02
[자료구조] 스택(Stack) (0)	2021.01.26
순환 알고리즘 (0)	2021.01.25

공부했던 자료 정리하는 용도입니다.

재배포, 수정하지 마세요.

우선순위 큐(priority queue)

큐에 우선순위의 개념을 도입한 자료구조
데이터들은 우선순위를 가지고 있고, 우선순위가 높은 데이터가 먼저 나가게 된다.
우선순위에 따라 스택이나 큐처럼 동작하기도 한다.

우선순위 큐 연산

객체 : n개의 element형의 우선 순위를 가진 요소들의 모임
연산 :
    create() ::= 우선순위 큐 생성
    init(q) ::= 우선순위 큐 q를 초기화
    is_empty(q) ::= 우선순위 큐 q가 비어있는지 검사
    is_full(q) ::= 우선순위 큐 q가 포화상태인지 검사
    insert(q, x) ::= 우선순위 큐 q에 요소 x를 추가
    delete(q) ::= 우선순위 큐로부터 가장 우선순위가 높은 요소를 삭제하고 해당 요소 반환
    find(q) ::= 우선순위가 가장 높은 요소를 반환

우선순위 큐 구현 방법

배열을 이용
- 정렬된 배열을 사용하는 경우
- 정렬되지 X 배열을 사용하는 경우
연결 리스트를 이용
- 정렬된 연결 리스트를 사용하는 경우
- 정렬되지 않은 연결 리스트를 사용하는 경우
힙(heap)을 이용

각 구현 방법에 따른 시간 복잡도

자료 구조	삽입 연산	삭제 연산
정렬된 배열 이용	$O(n)$	$O(1)$
정렬되지 않은 배열 이용	$O(1)$	$O(n)$ 우선순위가 높은 요소를 찾아야하기 때문
정렬된 연결 리스트를 이용	$O(n)$ 우선순위가 높은 요소를 찾아야 하기 때문	$O(1)$
정렬되지 않은 연결리스트 이용	$O(1)$ (처음에 삽입하는 경우)	$O(n)$ 배열과 마찬가지로 우선순위가 높은 요소를 찾아야 하기 때문
힙(heap)을 이용	$O(log_2n)$	$O(log_2n)$

힙(heap)

완전 이진트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다.
이진 탐색 트리와 달리 중복 값을 허용한다.
부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 이진트리이다.
일종의 느슨한 정렬 상태를 유지한다. (삭제 연산이 수행될 때 최대값(root)만 찾으면 되므로 전체를 정렬하지 않는다.)
최대값이나 최소값을 빠르게 찾을 때 유리하다.

힙의 종류

최대 힙(max heap)
: 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진트리
최소 힙(min heap)
: 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진트리

힙 구현 방법

배열을 이용한 구현
- 정렬된 배열 이용
- 정렬되지 X 배열 이용
- 구현을 쉽게 하기 위해서 인덱스 0은 사용하지 않는다.
- 연산을 통해 노드의 인덱스를 알 수 있다.
##왼쪽 자식의 인덱스 = (부모의 인덱스) * 2##
##오른쪽 자식의 인덱스 = (부모의 인덱스) * 2 + 1##
##부모의 인덱스 = (자식의 인덱스) / 2##
연결 리스트 이용

힙의 시간 복잡도

삽입 연산 : $O(log_2n)$
삭제 연산 : $O(log_2n)$

힙의 연산

삽입 연산
(1) 요소를 힙의 가장 마지막 노드로 삽입
(2) 부모 노드와 비교하여 부모 노드보다 클 경우 값 교환(부모 노드보다 작을 때까지 반복)
삭제 연산
(1) 루트 노드 삭제
(2) 빈 루트 자리에 힙의 마지막 노드를 가져옴
(3) 양쪽 자식 중 큰 값과 교환이 일어남(자식 노드보다 클 때까지 반복)

힙 정렬(heap sort)

시간 복잡도 : $O(nlog_2n)$ (전체 높이가 $log_2n$ 인 완전 이진트리이기 때문)

힙 응용

LPT 알고리즘(longest processing time first) : 가장 긴 작업을 우선적으로 할당하는 것
허프만 코드(Huffman codes)
ex) 영문자 빈도수를 이용한 데이터 압축

저작자표시 비영리 변경금지

'기타 > 자료구조' 카테고리의 다른 글

[자료구조] 그래프(graph) (0)	2021.07.31
[자료구조] 트리, 이진 트리, 이진 탐색 트리 (0)	2021.06.18
[자료구조] 큐(Queue), 덱(Deque) (0)	2021.02.02
[자료구조] 스택(Stack) (0)	2021.01.26
순환 알고리즘 (0)	2021.01.25

공부했던 자료 정리하는 용도입니다.

재배포, 수정하지 마세요.

우선순위 큐(priority queue)

큐에 우선순위의 개념을 도입한 자료구조
데이터들은 우선순위를 가지고 있고, 우선순위가 높은 데이터가 먼저 나가게 된다.
우선순위에 따라 스택이나 큐처럼 동작하기도 한다.

우선순위 큐 연산

객체 : n개의 element형의 우선 순위를 가진 요소들의 모임
연산 :
    create() ::= 우선순위 큐 생성
    init(q) ::= 우선순위 큐 q를 초기화
    is_empty(q) ::= 우선순위 큐 q가 비어있는지 검사
    is_full(q) ::= 우선순위 큐 q가 포화상태인지 검사
    insert(q, x) ::= 우선순위 큐 q에 요소 x를 추가
    delete(q) ::= 우선순위 큐로부터 가장 우선순위가 높은 요소를 삭제하고 해당 요소 반환
    find(q) ::= 우선순위가 가장 높은 요소를 반환

우선순위 큐 구현 방법

배열을 이용
- 정렬된 배열을 사용하는 경우
- 정렬되지 X 배열을 사용하는 경우
연결 리스트를 이용
- 정렬된 연결 리스트를 사용하는 경우
- 정렬되지 않은 연결 리스트를 사용하는 경우
힙(heap)을 이용

각 구현 방법에 따른 시간 복잡도

자료 구조	삽입 연산	삭제 연산
정렬된 배열 이용	$O(n)$	$O(1)$
정렬되지 않은 배열 이용	$O(1)$	$O(n)$ 우선순위가 높은 요소를 찾아야하기 때문
정렬된 연결 리스트를 이용	$O(n)$ 우선순위가 높은 요소를 찾아야 하기 때문	$O(1)$
정렬되지 않은 연결리스트 이용	$O(1)$ (처음에 삽입하는 경우)	$O(n)$ 배열과 마찬가지로 우선순위가 높은 요소를 찾아야 하기 때문
힙(heap)을 이용	$O(log_2n)$	$O(log_2n)$

힙(heap)

완전 이진트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다.
이진 탐색 트리와 달리 중복 값을 허용한다.
부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 이진트리이다.
일종의 느슨한 정렬 상태를 유지한다. (삭제 연산이 수행될 때 최대값(root)만 찾으면 되므로 전체를 정렬하지 않는다.)
최대값이나 최소값을 빠르게 찾을 때 유리하다.

힙의 종류

최대 힙(max heap)
: 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진트리
최소 힙(min heap)
: 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진트리

힙 구현 방법

배열을 이용한 구현
- 정렬된 배열 이용
- 정렬되지 X 배열 이용
- 구현을 쉽게 하기 위해서 인덱스 0은 사용하지 않는다.
- 연산을 통해 노드의 인덱스를 알 수 있다.
##왼쪽 자식의 인덱스 = (부모의 인덱스) * 2##
##오른쪽 자식의 인덱스 = (부모의 인덱스) * 2 + 1##
##부모의 인덱스 = (자식의 인덱스) / 2##
연결 리스트 이용

힙의 시간 복잡도

삽입 연산 : $O(log_2n)$
삭제 연산 : $O(log_2n)$

힙의 연산

삽입 연산
(1) 요소를 힙의 가장 마지막 노드로 삽입
(2) 부모 노드와 비교하여 부모 노드보다 클 경우 값 교환(부모 노드보다 작을 때까지 반복)
삭제 연산
(1) 루트 노드 삭제
(2) 빈 루트 자리에 힙의 마지막 노드를 가져옴
(3) 양쪽 자식 중 큰 값과 교환이 일어남(자식 노드보다 클 때까지 반복)

힙 정렬(heap sort)

시간 복잡도 : $O(nlog_2n)$ (전체 높이가 $log_2n$ 인 완전 이진트리이기 때문)

힙 응용

LPT 알고리즘(longest processing time first) : 가장 긴 작업을 우선적으로 할당하는 것
허프만 코드(Huffman codes)
ex) 영문자 빈도수를 이용한 데이터 압축

저작자표시 비영리 변경금지

'기타 > 자료구조' 카테고리의 다른 글

[자료구조] 그래프(graph) (0)	2021.07.31
[자료구조] 트리, 이진 트리, 이진 탐색 트리 (0)	2021.06.18
[자료구조] 큐(Queue), 덱(Deque) (0)	2021.02.02
[자료구조] 스택(Stack) (0)	2021.01.26
순환 알고리즘 (0)	2021.01.25

공부했던 자료 정리하는 용도입니다.

재배포, 수정하지 마세요.

우선순위 큐(priority queue)

큐에 우선순위의 개념을 도입한 자료구조
데이터들은 우선순위를 가지고 있고, 우선순위가 높은 데이터가 먼저 나가게 된다.
우선순위에 따라 스택이나 큐처럼 동작하기도 한다.

우선순위 큐 연산

객체 : n개의 element형의 우선 순위를 가진 요소들의 모임
연산 :
    create() ::= 우선순위 큐 생성
    init(q) ::= 우선순위 큐 q를 초기화
    is_empty(q) ::= 우선순위 큐 q가 비어있는지 검사
    is_full(q) ::= 우선순위 큐 q가 포화상태인지 검사
    insert(q, x) ::= 우선순위 큐 q에 요소 x를 추가
    delete(q) ::= 우선순위 큐로부터 가장 우선순위가 높은 요소를 삭제하고 해당 요소 반환
    find(q) ::= 우선순위가 가장 높은 요소를 반환

우선순위 큐 구현 방법

배열을 이용
- 정렬된 배열을 사용하는 경우
- 정렬되지 X 배열을 사용하는 경우
연결 리스트를 이용
- 정렬된 연결 리스트를 사용하는 경우
- 정렬되지 않은 연결 리스트를 사용하는 경우
힙(heap)을 이용

각 구현 방법에 따른 시간 복잡도

자료 구조	삽입 연산	삭제 연산
정렬된 배열 이용	$O(n)$	$O(1)$
정렬되지 않은 배열 이용	$O(1)$	$O(n)$ 우선순위가 높은 요소를 찾아야하기 때문
정렬된 연결 리스트를 이용	$O(n)$ 우선순위가 높은 요소를 찾아야 하기 때문	$O(1)$
정렬되지 않은 연결리스트 이용	$O(1)$ (처음에 삽입하는 경우)	$O(n)$ 배열과 마찬가지로 우선순위가 높은 요소를 찾아야 하기 때문
힙(heap)을 이용	$O(log_2n)$	$O(log_2n)$

힙(heap)

완전 이진트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다.
이진 탐색 트리와 달리 중복 값을 허용한다.
부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 이진트리이다.
일종의 느슨한 정렬 상태를 유지한다. (삭제 연산이 수행될 때 최대값(root)만 찾으면 되므로 전체를 정렬하지 않는다.)
최대값이나 최소값을 빠르게 찾을 때 유리하다.

힙의 종류

최대 힙(max heap)
: 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진트리
최소 힙(min heap)
: 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진트리

힙 구현 방법

배열을 이용한 구현
- 정렬된 배열 이용
- 정렬되지 X 배열 이용
- 구현을 쉽게 하기 위해서 인덱스 0은 사용하지 않는다.
- 연산을 통해 노드의 인덱스를 알 수 있다.
##왼쪽 자식의 인덱스 = (부모의 인덱스) * 2##
##오른쪽 자식의 인덱스 = (부모의 인덱스) * 2 + 1##
##부모의 인덱스 = (자식의 인덱스) / 2##
연결 리스트 이용

힙의 시간 복잡도

삽입 연산 : $O(log_2n)$
삭제 연산 : $O(log_2n)$

힙의 연산

삽입 연산
(1) 요소를 힙의 가장 마지막 노드로 삽입
(2) 부모 노드와 비교하여 부모 노드보다 클 경우 값 교환(부모 노드보다 작을 때까지 반복)
삭제 연산
(1) 루트 노드 삭제
(2) 빈 루트 자리에 힙의 마지막 노드를 가져옴
(3) 양쪽 자식 중 큰 값과 교환이 일어남(자식 노드보다 클 때까지 반복)

힙 정렬(heap sort)

시간 복잡도 : $O(nlog_2n)$ (전체 높이가 $log_2n$ 인 완전 이진트리이기 때문)

힙 응용

LPT 알고리즘(longest processing time first) : 가장 긴 작업을 우선적으로 할당하는 것
허프만 코드(Huffman codes)
ex) 영문자 빈도수를 이용한 데이터 압축

저작자표시 비영리 변경금지

'기타 > 자료구조' 카테고리의 다른 글

[자료구조] 그래프(graph) (0)	2021.07.31
[자료구조] 트리, 이진 트리, 이진 탐색 트리 (0)	2021.06.18
[자료구조] 큐(Queue), 덱(Deque) (0)	2021.02.02
[자료구조] 스택(Stack) (0)	2021.01.26
순환 알고리즘 (0)	2021.01.25

공부했던 자료 정리하는 용도입니다.

재배포, 수정하지 마세요.

우선순위 큐(priority queue)

큐에 우선순위의 개념을 도입한 자료구조
데이터들은 우선순위를 가지고 있고, 우선순위가 높은 데이터가 먼저 나가게 된다.
우선순위에 따라 스택이나 큐처럼 동작하기도 한다.

우선순위 큐 연산

객체 : n개의 element형의 우선 순위를 가진 요소들의 모임
연산 :
    create() ::= 우선순위 큐 생성
    init(q) ::= 우선순위 큐 q를 초기화
    is_empty(q) ::= 우선순위 큐 q가 비어있는지 검사
    is_full(q) ::= 우선순위 큐 q가 포화상태인지 검사
    insert(q, x) ::= 우선순위 큐 q에 요소 x를 추가
    delete(q) ::= 우선순위 큐로부터 가장 우선순위가 높은 요소를 삭제하고 해당 요소 반환
    find(q) ::= 우선순위가 가장 높은 요소를 반환

우선순위 큐 구현 방법

배열을 이용
- 정렬된 배열을 사용하는 경우
- 정렬되지 X 배열을 사용하는 경우
연결 리스트를 이용
- 정렬된 연결 리스트를 사용하는 경우
- 정렬되지 않은 연결 리스트를 사용하는 경우
힙(heap)을 이용

각 구현 방법에 따른 시간 복잡도

자료 구조	삽입 연산	삭제 연산
정렬된 배열 이용	$O(n)$	$O(1)$
정렬되지 않은 배열 이용	$O(1)$	$O(n)$ 우선순위가 높은 요소를 찾아야하기 때문
정렬된 연결 리스트를 이용	$O(n)$ 우선순위가 높은 요소를 찾아야 하기 때문	$O(1)$
정렬되지 않은 연결리스트 이용	$O(1)$ (처음에 삽입하는 경우)	$O(n)$ 배열과 마찬가지로 우선순위가 높은 요소를 찾아야 하기 때문
힙(heap)을 이용	$O(log_2n)$	$O(log_2n)$

힙(heap)

완전 이진트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다.
이진 탐색 트리와 달리 중복 값을 허용한다.
부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 이진트리이다.
일종의 느슨한 정렬 상태를 유지한다. (삭제 연산이 수행될 때 최대값(root)만 찾으면 되므로 전체를 정렬하지 않는다.)
최대값이나 최소값을 빠르게 찾을 때 유리하다.

힙의 종류

최대 힙(max heap)
: 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진트리
최소 힙(min heap)
: 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진트리

힙 구현 방법

배열을 이용한 구현
- 정렬된 배열 이용
- 정렬되지 X 배열 이용
- 구현을 쉽게 하기 위해서 인덱스 0은 사용하지 않는다.
- 연산을 통해 노드의 인덱스를 알 수 있다.
##왼쪽 자식의 인덱스 = (부모의 인덱스) * 2##
##오른쪽 자식의 인덱스 = (부모의 인덱스) * 2 + 1##
##부모의 인덱스 = (자식의 인덱스) / 2##
연결 리스트 이용

힙의 시간 복잡도

삽입 연산 : $O(log_2n)$
삭제 연산 : $O(log_2n)$

힙의 연산

삽입 연산
(1) 요소를 힙의 가장 마지막 노드로 삽입
(2) 부모 노드와 비교하여 부모 노드보다 클 경우 값 교환(부모 노드보다 작을 때까지 반복)
삭제 연산
(1) 루트 노드 삭제
(2) 빈 루트 자리에 힙의 마지막 노드를 가져옴
(3) 양쪽 자식 중 큰 값과 교환이 일어남(자식 노드보다 클 때까지 반복)

힙 정렬(heap sort)

시간 복잡도 : $O(nlog_2n)$ (전체 높이가 $log_2n$ 인 완전 이진트리이기 때문)

힙 응용

LPT 알고리즘(longest processing time first) : 가장 긴 작업을 우선적으로 할당하는 것
허프만 코드(Huffman codes)
ex) 영문자 빈도수를 이용한 데이터 압축

저작자표시 비영리 변경금지

'기타 > 자료구조' 카테고리의 다른 글

[자료구조] 그래프(graph) (0)	2021.07.31
[자료구조] 트리, 이진 트리, 이진 탐색 트리 (0)	2021.06.18
[자료구조] 큐(Queue), 덱(Deque) (0)	2021.02.02
[자료구조] 스택(Stack) (0)	2021.01.26
순환 알고리즘 (0)	2021.01.25

공부했던 자료 정리하는 용도입니다.

재배포, 수정하지 마세요.

우선순위 큐(priority queue)

큐에 우선순위의 개념을 도입한 자료구조
데이터들은 우선순위를 가지고 있고, 우선순위가 높은 데이터가 먼저 나가게 된다.
우선순위에 따라 스택이나 큐처럼 동작하기도 한다.

우선순위 큐 연산

객체 : n개의 element형의 우선 순위를 가진 요소들의 모임
연산 :
    create() ::= 우선순위 큐 생성
    init(q) ::= 우선순위 큐 q를 초기화
    is_empty(q) ::= 우선순위 큐 q가 비어있는지 검사
    is_full(q) ::= 우선순위 큐 q가 포화상태인지 검사
    insert(q, x) ::= 우선순위 큐 q에 요소 x를 추가
    delete(q) ::= 우선순위 큐로부터 가장 우선순위가 높은 요소를 삭제하고 해당 요소 반환
    find(q) ::= 우선순위가 가장 높은 요소를 반환

우선순위 큐 구현 방법

배열을 이용
- 정렬된 배열을 사용하는 경우
- 정렬되지 X 배열을 사용하는 경우
연결 리스트를 이용
- 정렬된 연결 리스트를 사용하는 경우
- 정렬되지 않은 연결 리스트를 사용하는 경우
힙(heap)을 이용

각 구현 방법에 따른 시간 복잡도

자료 구조	삽입 연산	삭제 연산
정렬된 배열 이용	$O(n)$	$O(1)$
정렬되지 않은 배열 이용	$O(1)$	$O(n)$ 우선순위가 높은 요소를 찾아야하기 때문
정렬된 연결 리스트를 이용	$O(n)$ 우선순위가 높은 요소를 찾아야 하기 때문	$O(1)$
정렬되지 않은 연결리스트 이용	$O(1)$ (처음에 삽입하는 경우)	$O(n)$ 배열과 마찬가지로 우선순위가 높은 요소를 찾아야 하기 때문
힙(heap)을 이용	$O(log_2n)$	$O(log_2n)$

힙(heap)

완전 이진트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다.
이진 탐색 트리와 달리 중복 값을 허용한다.
부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 이진트리이다.
일종의 느슨한 정렬 상태를 유지한다. (삭제 연산이 수행될 때 최대값(root)만 찾으면 되므로 전체를 정렬하지 않는다.)
최대값이나 최소값을 빠르게 찾을 때 유리하다.

힙의 종류

최대 힙(max heap)
: 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진트리
최소 힙(min heap)
: 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진트리

힙 구현 방법

배열을 이용한 구현
- 정렬된 배열 이용
- 정렬되지 X 배열 이용
- 구현을 쉽게 하기 위해서 인덱스 0은 사용하지 않는다.
- 연산을 통해 노드의 인덱스를 알 수 있다.
##왼쪽 자식의 인덱스 = (부모의 인덱스) * 2##
##오른쪽 자식의 인덱스 = (부모의 인덱스) * 2 + 1##
##부모의 인덱스 = (자식의 인덱스) / 2##
연결 리스트 이용

힙의 시간 복잡도

삽입 연산 : $O(log_2n)$
삭제 연산 : $O(log_2n)$

힙의 연산

삽입 연산
(1) 요소를 힙의 가장 마지막 노드로 삽입
(2) 부모 노드와 비교하여 부모 노드보다 클 경우 값 교환(부모 노드보다 작을 때까지 반복)
삭제 연산
(1) 루트 노드 삭제
(2) 빈 루트 자리에 힙의 마지막 노드를 가져옴
(3) 양쪽 자식 중 큰 값과 교환이 일어남(자식 노드보다 클 때까지 반복)

힙 정렬(heap sort)

시간 복잡도 : $O(nlog_2n)$ (전체 높이가 $log_2n$ 인 완전 이진트리이기 때문)

힙 응용

LPT 알고리즘(longest processing time first) : 가장 긴 작업을 우선적으로 할당하는 것
허프만 코드(Huffman codes)
ex) 영문자 빈도수를 이용한 데이터 압축

저작자표시 비영리 변경금지

'기타 > 자료구조' 카테고리의 다른 글

[자료구조] 그래프(graph) (0)	2021.07.31
[자료구조] 트리, 이진 트리, 이진 탐색 트리 (0)	2021.06.18
[자료구조] 큐(Queue), 덱(Deque) (0)	2021.02.02
[자료구조] 스택(Stack) (0)	2021.01.26
순환 알고리즘 (0)	2021.01.25

공부했던 자료 정리하는 용도입니다.

재배포, 수정하지 마세요.

우선순위 큐(priority queue)

큐에 우선순위의 개념을 도입한 자료구조
데이터들은 우선순위를 가지고 있고, 우선순위가 높은 데이터가 먼저 나가게 된다.
우선순위에 따라 스택이나 큐처럼 동작하기도 한다.

우선순위 큐 연산

객체 : n개의 element형의 우선 순위를 가진 요소들의 모임
연산 :
    create() ::= 우선순위 큐 생성
    init(q) ::= 우선순위 큐 q를 초기화
    is_empty(q) ::= 우선순위 큐 q가 비어있는지 검사
    is_full(q) ::= 우선순위 큐 q가 포화상태인지 검사
    insert(q, x) ::= 우선순위 큐 q에 요소 x를 추가
    delete(q) ::= 우선순위 큐로부터 가장 우선순위가 높은 요소를 삭제하고 해당 요소 반환
    find(q) ::= 우선순위가 가장 높은 요소를 반환

우선순위 큐 구현 방법

배열을 이용
- 정렬된 배열을 사용하는 경우
- 정렬되지 X 배열을 사용하는 경우
연결 리스트를 이용
- 정렬된 연결 리스트를 사용하는 경우
- 정렬되지 않은 연결 리스트를 사용하는 경우
힙(heap)을 이용

각 구현 방법에 따른 시간 복잡도

자료 구조	삽입 연산	삭제 연산
정렬된 배열 이용	$O(n)$	$O(1)$
정렬되지 않은 배열 이용	$O(1)$	$O(n)$ 우선순위가 높은 요소를 찾아야하기 때문
정렬된 연결 리스트를 이용	$O(n)$ 우선순위가 높은 요소를 찾아야 하기 때문	$O(1)$
정렬되지 않은 연결리스트 이용	$O(1)$ (처음에 삽입하는 경우)	$O(n)$ 배열과 마찬가지로 우선순위가 높은 요소를 찾아야 하기 때문
힙(heap)을 이용	$O(log_2n)$	$O(log_2n)$

힙(heap)

완전 이진트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다.
이진 탐색 트리와 달리 중복 값을 허용한다.
부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 이진트리이다.
일종의 느슨한 정렬 상태를 유지한다. (삭제 연산이 수행될 때 최대값(root)만 찾으면 되므로 전체를 정렬하지 않는다.)
최대값이나 최소값을 빠르게 찾을 때 유리하다.

힙의 종류

최대 힙(max heap)
: 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진트리
최소 힙(min heap)
: 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진트리

힙 구현 방법

배열을 이용한 구현
- 정렬된 배열 이용
- 정렬되지 X 배열 이용
- 구현을 쉽게 하기 위해서 인덱스 0은 사용하지 않는다.
- 연산을 통해 노드의 인덱스를 알 수 있다.
##왼쪽 자식의 인덱스 = (부모의 인덱스) * 2##
##오른쪽 자식의 인덱스 = (부모의 인덱스) * 2 + 1##
##부모의 인덱스 = (자식의 인덱스) / 2##
연결 리스트 이용

힙의 시간 복잡도

삽입 연산 : $O(log_2n)$
삭제 연산 : $O(log_2n)$

힙의 연산

삽입 연산
(1) 요소를 힙의 가장 마지막 노드로 삽입
(2) 부모 노드와 비교하여 부모 노드보다 클 경우 값 교환(부모 노드보다 작을 때까지 반복)
삭제 연산
(1) 루트 노드 삭제
(2) 빈 루트 자리에 힙의 마지막 노드를 가져옴
(3) 양쪽 자식 중 큰 값과 교환이 일어남(자식 노드보다 클 때까지 반복)

힙 정렬(heap sort)

시간 복잡도 : $O(nlog_2n)$ (전체 높이가 $log_2n$ 인 완전 이진트리이기 때문)

힙 응용

LPT 알고리즘(longest processing time first) : 가장 긴 작업을 우선적으로 할당하는 것
허프만 코드(Huffman codes)
ex) 영문자 빈도수를 이용한 데이터 압축

저작자표시 비영리 변경금지

'기타 > 자료구조' 카테고리의 다른 글

[자료구조] 그래프(graph) (0)	2021.07.31
[자료구조] 트리, 이진 트리, 이진 탐색 트리 (0)	2021.06.18
[자료구조] 큐(Queue), 덱(Deque) (0)	2021.02.02
[자료구조] 스택(Stack) (0)	2021.01.26
순환 알고리즘 (0)	2021.01.25

공부했던 자료 정리하는 용도입니다.

재배포, 수정하지 마세요.

우선순위 큐(priority queue)

큐에 우선순위의 개념을 도입한 자료구조
데이터들은 우선순위를 가지고 있고, 우선순위가 높은 데이터가 먼저 나가게 된다.
우선순위에 따라 스택이나 큐처럼 동작하기도 한다.

우선순위 큐 연산

객체 : n개의 element형의 우선 순위를 가진 요소들의 모임
연산 :
    create() ::= 우선순위 큐 생성
    init(q) ::= 우선순위 큐 q를 초기화
    is_empty(q) ::= 우선순위 큐 q가 비어있는지 검사
    is_full(q) ::= 우선순위 큐 q가 포화상태인지 검사
    insert(q, x) ::= 우선순위 큐 q에 요소 x를 추가
    delete(q) ::= 우선순위 큐로부터 가장 우선순위가 높은 요소를 삭제하고 해당 요소 반환
    find(q) ::= 우선순위가 가장 높은 요소를 반환

우선순위 큐 구현 방법

배열을 이용
- 정렬된 배열을 사용하는 경우
- 정렬되지 X 배열을 사용하는 경우
연결 리스트를 이용
- 정렬된 연결 리스트를 사용하는 경우
- 정렬되지 않은 연결 리스트를 사용하는 경우
힙(heap)을 이용

각 구현 방법에 따른 시간 복잡도

자료 구조	삽입 연산	삭제 연산
정렬된 배열 이용	$O(n)$	$O(1)$
정렬되지 않은 배열 이용	$O(1)$	$O(n)$ 우선순위가 높은 요소를 찾아야하기 때문
정렬된 연결 리스트를 이용	$O(n)$ 우선순위가 높은 요소를 찾아야 하기 때문	$O(1)$
정렬되지 않은 연결리스트 이용	$O(1)$ (처음에 삽입하는 경우)	$O(n)$ 배열과 마찬가지로 우선순위가 높은 요소를 찾아야 하기 때문
힙(heap)을 이용	$O(log_2n)$	$O(log_2n)$

힙(heap)

완전 이진트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다.
이진 탐색 트리와 달리 중복 값을 허용한다.
부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 이진트리이다.
일종의 느슨한 정렬 상태를 유지한다. (삭제 연산이 수행될 때 최대값(root)만 찾으면 되므로 전체를 정렬하지 않는다.)
최대값이나 최소값을 빠르게 찾을 때 유리하다.

힙의 종류

최대 힙(max heap)
: 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진트리
최소 힙(min heap)
: 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진트리

힙 구현 방법

배열을 이용한 구현
- 정렬된 배열 이용
- 정렬되지 X 배열 이용
- 구현을 쉽게 하기 위해서 인덱스 0은 사용하지 않는다.
- 연산을 통해 노드의 인덱스를 알 수 있다.
##왼쪽 자식의 인덱스 = (부모의 인덱스) * 2##
##오른쪽 자식의 인덱스 = (부모의 인덱스) * 2 + 1##
##부모의 인덱스 = (자식의 인덱스) / 2##
연결 리스트 이용

힙의 시간 복잡도

삽입 연산 : $O(log_2n)$
삭제 연산 : $O(log_2n)$

힙의 연산

삽입 연산
(1) 요소를 힙의 가장 마지막 노드로 삽입
(2) 부모 노드와 비교하여 부모 노드보다 클 경우 값 교환(부모 노드보다 작을 때까지 반복)
삭제 연산
(1) 루트 노드 삭제
(2) 빈 루트 자리에 힙의 마지막 노드를 가져옴
(3) 양쪽 자식 중 큰 값과 교환이 일어남(자식 노드보다 클 때까지 반복)

힙 정렬(heap sort)

시간 복잡도 : $O(nlog_2n)$ (전체 높이가 $log_2n$ 인 완전 이진트리이기 때문)

힙 응용

LPT 알고리즘(longest processing time first) : 가장 긴 작업을 우선적으로 할당하는 것
허프만 코드(Huffman codes)
ex) 영문자 빈도수를 이용한 데이터 압축

저작자표시 비영리 변경금지

'기타 > 자료구조' 카테고리의 다른 글

[자료구조] 그래프(graph) (0)	2021.07.31
[자료구조] 트리, 이진 트리, 이진 탐색 트리 (0)	2021.06.18
[자료구조] 큐(Queue), 덱(Deque) (0)	2021.02.02
[자료구조] 스택(Stack) (0)	2021.01.26
순환 알고리즘 (0)	2021.01.25

공부했던 자료 정리하는 용도입니다.

재배포, 수정하지 마세요.

우선순위 큐(priority queue)

큐에 우선순위의 개념을 도입한 자료구조
데이터들은 우선순위를 가지고 있고, 우선순위가 높은 데이터가 먼저 나가게 된다.
우선순위에 따라 스택이나 큐처럼 동작하기도 한다.

우선순위 큐 연산

객체 : n개의 element형의 우선 순위를 가진 요소들의 모임
연산 :
    create() ::= 우선순위 큐 생성
    init(q) ::= 우선순위 큐 q를 초기화
    is_empty(q) ::= 우선순위 큐 q가 비어있는지 검사
    is_full(q) ::= 우선순위 큐 q가 포화상태인지 검사
    insert(q, x) ::= 우선순위 큐 q에 요소 x를 추가
    delete(q) ::= 우선순위 큐로부터 가장 우선순위가 높은 요소를 삭제하고 해당 요소 반환
    find(q) ::= 우선순위가 가장 높은 요소를 반환

우선순위 큐 구현 방법

배열을 이용
- 정렬된 배열을 사용하는 경우
- 정렬되지 X 배열을 사용하는 경우
연결 리스트를 이용
- 정렬된 연결 리스트를 사용하는 경우
- 정렬되지 않은 연결 리스트를 사용하는 경우
힙(heap)을 이용

각 구현 방법에 따른 시간 복잡도

자료 구조	삽입 연산	삭제 연산
정렬된 배열 이용	$O(n)$	$O(1)$
정렬되지 않은 배열 이용	$O(1)$	$O(n)$ 우선순위가 높은 요소를 찾아야하기 때문
정렬된 연결 리스트를 이용	$O(n)$ 우선순위가 높은 요소를 찾아야 하기 때문	$O(1)$
정렬되지 않은 연결리스트 이용	$O(1)$ (처음에 삽입하는 경우)	$O(n)$ 배열과 마찬가지로 우선순위가 높은 요소를 찾아야 하기 때문
힙(heap)을 이용	$O(log_2n)$	$O(log_2n)$

힙(heap)

완전 이진트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다.
이진 탐색 트리와 달리 중복 값을 허용한다.
부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 이진트리이다.
일종의 느슨한 정렬 상태를 유지한다. (삭제 연산이 수행될 때 최대값(root)만 찾으면 되므로 전체를 정렬하지 않는다.)
최대값이나 최소값을 빠르게 찾을 때 유리하다.

힙의 종류

최대 힙(max heap)
: 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진트리
최소 힙(min heap)
: 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진트리

힙 구현 방법

배열을 이용한 구현
- 정렬된 배열 이용
- 정렬되지 X 배열 이용
- 구현을 쉽게 하기 위해서 인덱스 0은 사용하지 않는다.
- 연산을 통해 노드의 인덱스를 알 수 있다.
##왼쪽 자식의 인덱스 = (부모의 인덱스) * 2##
##오른쪽 자식의 인덱스 = (부모의 인덱스) * 2 + 1##
##부모의 인덱스 = (자식의 인덱스) / 2##
연결 리스트 이용

힙의 시간 복잡도

삽입 연산 : $O(log_2n)$
삭제 연산 : $O(log_2n)$

힙의 연산

삽입 연산
(1) 요소를 힙의 가장 마지막 노드로 삽입
(2) 부모 노드와 비교하여 부모 노드보다 클 경우 값 교환(부모 노드보다 작을 때까지 반복)
삭제 연산
(1) 루트 노드 삭제
(2) 빈 루트 자리에 힙의 마지막 노드를 가져옴
(3) 양쪽 자식 중 큰 값과 교환이 일어남(자식 노드보다 클 때까지 반복)

힙 정렬(heap sort)

시간 복잡도 : $O(nlog_2n)$ (전체 높이가 $log_2n$ 인 완전 이진트리이기 때문)

힙 응용

LPT 알고리즘(longest processing time first) : 가장 긴 작업을 우선적으로 할당하는 것
허프만 코드(Huffman codes)
ex) 영문자 빈도수를 이용한 데이터 압축

저작자표시 비영리 변경금지

'기타 > 자료구조' 카테고리의 다른 글

[자료구조] 그래프(graph) (0)	2021.07.31
[자료구조] 트리, 이진 트리, 이진 탐색 트리 (0)	2021.06.18
[자료구조] 큐(Queue), 덱(Deque) (0)	2021.02.02
[자료구조] 스택(Stack) (0)	2021.01.26
순환 알고리즘 (0)	2021.01.25

내 블로그 - 관리자 홈 전환	`Q` `Q`
새 글 쓰기	`W` `W`

글 수정 (권한 있는 경우)	`E` `E`
댓글 영역으로 이동	`C` `C`

이 페이지의 URL 복사	`S` `S`
맨 위로 이동	`T` `T`
티스토리 홈 이동	`H` `H`
단축키 안내	`Shift` + `/` `⇧` + `/`

pridiot