Python) Heap 정리 및 heap sort 구현해보기

우연히 찾은 컴퓨터 알고리즘 강의인데, 출퇴근길에 들어보고 있다. 자료 구조 중의 하나인 Heap에 대해 알아보고 구현하는 것까지 해보려고 한다. 일단 Heap을 사용하는 이유부터 알아보자 Heap은 Prioirty Queue와 같이 우선순위가 존재하는 자료 구조이다. Heap(힙)이란? 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다. 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조 완전 이진 트리(complete binary tree)에 가까운 형태 이진트리(Binary tree)는 각 노드의 자식수가 2 이하인 경우 완전 이진 트리는 Root 노드부터 Leaf 노드까지 빠짐없이 채워져 있는 트리 종류 최대힙 (max-heap property) 부모..

2022.04.08