코딩복습장

이번 글에서는 Heap sort를 구현해볼 것이다.  heap은 max heap을 사용할 것이다.  우리는 배열에 데이터를 넣고 heap으로 사용할 것이다.  이전 글에서 우리는 배열로 complete binary tree를 만들때 부모노드를 구하는 방식을 배웠다. 여기서 자식노드를 구하고 싶을 경우왼쪽 자식노드: 부모노드 index x 2오른쪽 자식노드: 부모노드 index x 2 + 1이 공식은 배열의 0번째 index가 비워져 있을 때의 공식이다.  배열을 모두 채웠을 경우는 공식이 아래와 같아진다. (한칸씩 배열이 왼쪽으로 밀림) 부모 = 배열의 길이 // 2 - 1왼쪽 자식 = 부모 * 2 + 1오른쪽 자식 = 왼쪽 자식 +1우리는 이 공식을 이용하여 힙 정렬을 구현할 것이다.  우리는 가장 오..

이번 글에서는 heap과 heap의 구현, heap sort의 구현에 대해 다뤄보려고 한다.  내용이 너무 많아 이번 포스팅에서는 개념을 다루고 다음 포스팅에 구현을 다루려고 한다. 🔹 힙(heap)힙은 최댓값, 최솟값을 빨리 알아내기 위해 고안된 완전 이진트리(complete binary tree)를 기본으로 하는 자료구조이다.  - 출처: 위키백과  힙은 크게 두 가지 조건은 만족하는 자료구조라고 볼 수 있다.  1. 완전 이진트리 : 노드를 삽입할때 왼쪽부터 차례대로 삽입하는 트리  2. Partial Order: 데이터 일부분에 대해서 어떠한 특징을 만족하는 것 (반대는 total order가 있음, 순서 만족)-> 오름차순, 내림차순을 만족하지는 않지만 부모 노드가 자식노드보다는 항상 크거나 ..