Heap

힙

이진트리

• 모든 노드들이 2개의 서브트리를 갖는 트리
• 각 노드가 자식 노드를 최대한 2개 까지만 가질 수 있는 트리
  • 왼쪽 자식 노드
  • 오른쪽 자식 노드
• 레벨 i에서의 노드의 최대 개수는 2^i 개
• 높이가 h이인 이진트리가 가질 수 있는 노드의 최소 개수는 (h+1)개이며, 최대 개수는 (2^(h+1)-1)개이다.

완전 이진트리

• 높이가 h이고 노드 수가 n개일 때, 포화 이진트리의 노드 번호 1번부터 n번까지 빈 자리가 없는 이진트리

힙

• 완전 이진트리에 있는 노드 중에서 키값이 가장 큰 노드나 키 값이 가장 작은 노드를 찾기 위해서 만든 자료구조
• 최소힙은 가장 작은 값이 항상 루트에 위치, 최대힙은 가장 큰 값이 항상 루트에 위치
• 힙의 키를 우선순위로 활용하여 우선순위 큐를 구현할 수 있다.
• 힙은 정렬된 구조가 아니며 항상 부모가 자식보다 크거나 같다는 조건만 만족할 뿐, 정렬되어 있지는 않다.
• 수행시간은 기본적으로 트리의 높이와 같기 때문에 logN인데, 각 모든 정점에 대해서 다 힙 정렬을 해야하기 때문에 N을 곱해줘서 NlogN이다.

최대 힙

• 키 값이 가장 큰 노드를 찾기 위한 완전 이진 트리
• (부모노드의 키값>자식노드의 키값)
• 루트 노드 : 키값이 가장 큰 노드

최소 힙

• 키값이 가장 작은 노드를 찾기 위한 완전 이진 트리
• (부모노드의 키 값 < 자식노드의 키값)
• 루트 노드 : 키값이 가장 작은 노드

힙 연산

#삽입 
a = 10 

def heap_insert(heap,a) :
    #힙에 가장 마지막에 자료를 넣는다. 
    heap.append(a)
    #힙의 길이
    last = len(heap)
    #루트노드가 아니면 
    while last != 1  :
        #부모는 현재에서 2를 나눈 몫 
        parent = lats//2
        #부모가 자식보다 작으면 위치 변경 
        if heap[parent] < heap[last] :
            heap[parent],heap[last] = hepa[last],heap[parent]
            last = parent
        else :
            break 
#삭제 
def heap_delete(heap) :
    #힙의 루트를 초기화 
    heap[1] = None 
    #트리의 루트에 마지막 값을 넣음 
    heap[1] = heap.pop()
    
    #루트의 번호 
    i = 1
    #힙의 마지막이 아니면 
    while 2*i+1 <len(heap) :
        #자식들중에 더 큰 값을 기준으로 
        if heap[2*i]<heap[2*i+1] :
            tmp = 2 *i +1 
        else :
            tmp = 2*i 
		#부모보다 자식이 크면 위치 변경 
        if heap[i] > heap[tmp] :
            heap[i],heap[tmp] = heap[tmp],heap[i]
            i = tmp 

힙큐는 최소힙만 다룬다.

힙큐를 최대값으로 쓰려면 다 마이너스 처리한 후 최소값을 찾는다. 그리고 최대값을 찾으면 된다.