Heap 데이터 구조에 대한 깨달음

이번에 처음 공부해 본 Heap 데이터 구조,, 공부하며 고민했던 점, 궁금증을 정리해 본다.

Heap의 기본적인 개념은 인터넷에 많아욤!

 

궁금했던 점 1) parent - child index 관계...왜?

Heap은 memory의 관점에서 정말 중요한 특징이 있다.

앞선 BST, AVL tree와는 달리 포인터로 node를 linking하지 않아도 된다는 것이다.

Heap은 1차원 array로 충분히 그 structure를 만들 수 있다.

 

그 이유는 무엇일까?

parent - 2 child 사이의 index 관계가 명확하기 때문이다.

그런데 index끼리의 관계가 그렇게 되는지를 간단하게 수학적 귀납법으로 증명해 보았다.

Lecture note of Korea University Prof. Hwangnam Kim & short proof using M.I

궁금했던 점 2) (AVL tree with Max, Min pointer) vs Heap

Heap은 결국 최대 혹은 최소값을 O(1)으로 얻는 것에 의미가 있다면 AVL tree에서 max, min pointer만

따로 둔다면 똑같은 거 아닌가? 오히려 중간 값도 얻을 수 있는 AVL tree만 쓰면 안 되나?라는 의문이 있었다.

 

각 operation마다 Complexity를 확인해 보자.

1. insert : O(log n) , insert 후 아래에서부터 push up을 tree height 만큼

2. delete : O(log n) , delete 후 위에서부터 push down을 tree height 만큼

 

실제로 표로 비교해 보아도 AVL tree보다 나은 게 무엇인지 모르겠다.

AVL tree with pointer vs Heap

Complexity 더 들여다보기

교수님께 여쭤보니 이는 complexity 뿐만 아니라 memory 할당 관점에서 바라보아야 한다고 하였다.

일단 AVL tree의 경우에는 data 뿐만 아니라 left, right node를 가리킬 수 있는 포인터가 따로 저장되어 있어야 하고,

실제로 컴퓨터 CPU가 cache 에 데이터를 가져올 때 더 heap 구조가 더 compact하게 가져올 수 있다.

이 외에도 여러 이유가 있을 것이라고 하셨다.

다른 이유가 있으면 댓글 부탁드립니다.

반론이나 질문은 환영입니다.