힙

힙 -> 완전 이진 트리 이어야함. ; 왼쪽 부터 꽉 채워져 있는 것.

 

index 계산:

계산 편의를 위해 인덱스를 1부터 사용: parent: x. left: 2x. right: 2x + 1

 

def __len__(self):...

def _percolate_up(self): # percolate 스며들다
	cur = len(self)
    parent = cur // 2 # left : 2* cur, right = 2*cur + 1 이므로, parent는 cur//2
    
    while parent > 0:
    	if self.items[cur] > self.items[parent]:
        	self.items[cur], self.items[parent] = self.items[parent], self.items[cur]
            
            cur = parent
            parent = cur // 2
            
def extract(self):
	if len(self) < 1:
    	return None
        
    root = self.items[1]
    self.items[1] = self.items[-1]
    self.items.pop()
    self._percolate_down(1)
    return root

 

힙에서의 pop과 insert는 어떻게 실행될까.

 

1) insert

맨 끝에다가 값을 넣고, parent 노드와 비교하면서, 올라나간다.

 

2) pop 

루트는 return 하고, 맨 끝에 있는 노드를 위로 올려, 자식 노드중 큰 노드와 자리를 바꾼다.