힙정렬

18 Jan 2021 in Algorithms

힙의 형태 : 완전 이진 트리에 가깝다.

완전 이진 트리는 다음과 같이 leaf 노드가 왼쪽 부터 차례대로 채워져 있다. b그림은 완전이진트리 아님.

힙 구조

최대힙 특성 (Max-Heap Property) : 각 하위 트리의 root 노드 값이 가장 크다.
최소힙 특성 (Min-Heap Property): 각 하위 트리의 root 노드 값이 가장 작다.

힙을 배열에 저장하면 다음과 같이 검색이 가능하다
- i번째 요소의 부모는 int(i/2) 번째에 저장돼있다. (완전 이진 트리므로)
- i 번째 요소의 왼쪽 자식은 2i에 저장돼있고, 오른쪽 자식은 2i+1 에 저장돼있다.
노드의 높이 : log(n)

힙 특성 관리(max-Heapify)

새 원소가 힙에 들어왔을 때, 주어진 노드의 값을 흘러내리게 해서 max-heap 특성에 맞게 변경
- n개의 원소가 있다면, n/2에서 역순으로 1까지 확인하면서 heapify 잘 되었는지 확인한다.
트리에서 최대값이 추출하고 다시 Heapify하게 하기
- 루트값과 가장 마지막에 있는 값의 위치를 바꿔주고, 최대값 추출, 그리고 max heapify 수행하게 해준다.

알고리즘 설명

IDEA :

max-heap 구조를 만든다.
n/2에서 역순으로 2까지 본다.
root와 맨 마지막 leaf 노드의 값을 바꿔준다. 그리고 leaf하나 버려 그리고 heapify. 이걸 반복한다.

성능 분석

시간 복잡도 : O(nlogn)
sort in place

JAVA 코드

child의 parent 는 int(child_ind/2) 하면 나온다 를 염두에 두고 코딩을 해봐라.

static int[] ary = {11,1,120,89,3,5,2,122,13,22,123,1222};
public static void main(String[] args) {
    heap_sort(ary,(ary.length-1)/2);
    System.out.println("결과들 : " +Arrays.toString(ary) );
}

public static void heap_sort(int[] ary,int parent){
    if (parent ==-1) {return;}
    int left = parent*2+1;
    int right = parent*2+2;
    if (ary[left]>ary[parent]) {
        if(ary.length>right) {
            if(ary[left]>ary[right]) {
                int tmp =ary[left];
                ary[left]= ary[parent];
                ary[parent]=tmp;
                if(left<=(ary.length-1)/2) {
                    heap_sort(ary,left);}
            }else {
                int tmp =ary[right];
                ary[right]= ary[parent];
                ary[parent]=tmp;
                if(left<=(ary.length-1)/2) {
                    heap_sort(ary,right);}
            }
        }else {
            int tmp =ary[left];
            ary[left]= ary[parent];
            ary[parent]=tmp;
            if(left<=(ary.length-1)/2) {
                heap_sort(ary,left);}
        }
    }
    heap_sort(ary,parent-1);
}

PYTHON 코드

2017년도 데관활에서 했던 코드.. 여기서 inplace랑 bottom up 이랑 비교했는데,, 결과는 다음과같았다.
inplace sort가 더 빠르다. 파이썬 처음 배울때라 왜 이런걸 비교하지 싶었는데 성능땜이었구나.. 성능이 왜 중요하지 이랬는데 이런 쓰잘데기 없는 의문은 그냥 처음부터 싹을 자르길…
그때는 알았고 지금은 까먹었다.. 다시 공부하기.

import datetime as dt
class Heap():
     def __init__(self,lst):
          self._data=lst
 
     def _parent(self,j):
          return (j-1)//2
     def _left(self,j):
          return 2*j+1
     def _right(self,j):
          return 2*j+2
     def _has_left(self,j):
          return self._left(j)<len(self._data)

     def _has_right(self,j):
          return self._right(j)<len(self._data)
     
     def _upheap(self,j):
          parent=self._parent(j)
          if j>0 and self._data[j]<self._data[parent]:
               self._swap(j,parent)
               self._upheap(parent)

     
     def _downheap(self,j):
          if self._has_left(j):
               left=self._left(j)
               big=left
               if self._has_right(j):
                    right=self._right(j)
                    if self._data[right]>self._data[left]:
                         big=right
               if self._data[big]>self._data[j]:
                    self._data[big],self._data[j]=self._data[j],self._data[big]
                    self._downheap(big)
          
     def _sort(self):
          alst=[]
          while len(self._data)!=0:
               self._data[0],self._data[-1]=self._data[-1],self._data[0]
               alst.insert(0,self._data[-1])
               self._data=self._data[:-1]
               self._downheap(0)
          return alst

     def _ipdownheap(self,j,l):
          if self._has_left(j):
               left=self._left(j)
               if left>=l:
                    return
               small_child=left
               if self._has_right(j):
                    right=self._right(j)
                    if self._data[right]>self._data[left]:
                         small_child=right
               if self._data[small_child]>self._data[j]:
                    self._data[small_child],self._data[j]=self._data[j],self._data[small_child]
                    self._ipdownheap(small_child,l)

     def _ipsort(self):
          global ind
          global l
          ind=0
          for _ in range(l-1):
               self._data[0],self._data[l]=self._data[l],self._data[0]
               l-=1
               self._ipdownheap(0,l)
          return self._data

class busort:
     def __init__(self,data):
          self._data=data
          if len(self._data)>1:
               self._heapify()        
     def __len__(self):
          return len(self._data)
     def _has_left(self,j):
          return self._left(j)<len(self._data)
     def _has_right(self,j):
          return self._right(j)<len(self._data)
     def _parent(self,j):
          return (j-1)//2
     def _left(self,j):
          return 2*j+1
     def _right(self,j):
          return 2*j+2
     def _heapify(self):
          start=self._parent(len(self))

          for j in range(start,-1,-1):
               self._buheap(j)
     def _buheap(self,j):
          if self._has_left(j):
               left=self._left(j)
               big=left
               if self._has_right(j):
                    right=self._right(j)
                    if self._data[right]>self._data[left]:
                         big=right
               if self._data[big]>self._data[j]:
                    self._data[big],self._data[j]=self._data[j],self._data[big]
                    self._buheap(big)

def compare(n):          
     alist=[]
     for x in range(n):
          alist.append(x)
     b=busort(alist)
     a=Heap(alist)
     global l
     l=len(alist)-1
     t1=dt.datetime.now()
     a._ipsort()
     t2=dt.datetime.now()
     t3=dt.datetime.now()
     a._sort()
     t4=dt.datetime.now()
     print(n,'일때: ''\ninplace sort : ',(t2-t1),'sort: ',(t4-t3))
compare(100)
compare(500)
compare(1000)
compare(10000)
compare(20000)
compare(30000)
compare(50000)

힙정렬

알고리즘 설명

성능 분석

JAVA 코드

PYTHON 코드

Yeji 'Callie'

Error

알고리즘 설명

성능 분석

JAVA 코드

PYTHON 코드

Templates (for web app):

Error