Java 힙Heap

힙Heap

자료구조 중 하나로 우선순위 큐Queue를 이용하여 만든 완전 이진 트리

우선순위 큐Queue
우선 순위를 가진 데이터들이 우선 순위대로 사용 되는 큐Queue

최댓값 또는 최솟값을 찾는데 이용되며, 중복 된 값을 허용한다.

최소힙
부모 노드(상위 노드)보다 자식노드(하위 노드)의 키값이 작거나 같음
최대힙
부모 노드(상위노드)보다 자식노드(하위 노드)의 키값이 크거나 같음

---

구현

• 표준 자료 저장방법은 배열이다.
• 일반적으로 힙의 시작 배열은 1로 한다.
• 기존 노드 번호는 새로운 노드에 의해 변하지 않는다.

  노드의 관계

  • 왼쪽 자식 노드의 인덱스 = 부모 노드의 인덱스 * 2
  • 오른쪽 자식 노드의 인덱스 = 부모 노드의 인덱스 * 2 + 1
  • 부모 노드의 인덱스 = 자식 노드의 인덱스 / 2
    

삽입
1. 새로운 요소Value 입력
2. 가장 하위 자식노드와 비교
3. 비교값이 참이면 상위 노드와 삽입 노드의 자리 교체

삭제
1. 원하는 노드 삭제
2. 해당 루트중 최하위 노드를 최상위 노드(가장 부모 노드)로 위치
3. 자식 노드와 비교
4. 비교값이 참이면 자식 노드와 자리 교체

---

메모리

• 메소드 영역
  static 메모리 영역이라고도 하며, 전역변수와 static변수의 저장 영역
• 스택Stack 영역
  지역 변수, 인자, 리턴값, 메소드 내의 기본형 변수, Heap영역에 생성된 객체들의 주소 등의 저장 영역
• 힙Heap 영역
  프로그램에서 사용되는 모든 인스턴스 변수들이 저장되는 영역이며, new를 사용하여 객체를 생성하면 힙 영역에 저장되고, 메모리 공간이 동적으로 할당되고 해제되며 메모리의 낮은 주소에서부터 높은 주소로의 할당이 이루어짐

---

시간복잡도

O(log n)