목록Algorithm/자료구조 (1)
개발일기
자료구조 힙 make_heap
힙성질 1. 부모노드가 자식노드보다 값이 커야한다. 2. 완전한 이진트리 형태로 구성되어 있다. 위에 이진트리를 보면 힙성질을 만족하지 않는다. 왜냐면 부모노드가 자식노드보다 값이 작기 때문이다. 그래서 서로 위치를 바꿔주는 작업을 해야하는데 이러한 작업을 make_heap이라고 한다. make_heap은 heapify-down이라는 연산을 계속해주어야함. 리프노드는 각각 파란색 화살표로 가르키고 있다. 리프노드는 자기의 값과 비교할 자식노드가 없기 때문에 하나의 힙 성질을 띄고 있는 작은 힙이된다. 이러한 이유때문에 사실 리프노드를 살펴볼 필요가 없다. 1의 왼쪽 자식 노드와 오른쪽 자식노드를 살펴보자. 1은 A[3]에 있다. 위에와 같은 표현방법으로 표현할 때의 장점은 1의 왼쪽 자식노드와 오른쪽 자..
Algorithm/자료구조
2023. 7. 18. 08:52