# 예1 - 10 노드의 부모 노드 인덱스
2 // 2
# 예1 - 15 노드의 왼쪽 자식 노드 인덱스 번호
1 * 2
# 예1 - 15 노드의 오른쪽 자식 노드 인덱스 번호
1 * 2 + 1
class Heap:
def __init__(self, data):
self.heap_array = list()
self.heap_array.append(data)
heap = Heap(1)
heap.heap_array
class Heap:
def __init__(self, data):
self.heap_array = list()
self.heap_array.append(None) # 인덱스 번호는 1번부터
self.heap_array.append(data)
def insert(self, data):
if len(self.heap_array) == 1:
self.heap_array.append(data)
return True
self.heap_array.append(data)
return True
class Heap:
def __init__(self, data):
self.heap_array = list()
self.heap_array.append(None) # 인덱스 번호는 1번부터
self.heap_array.append(data)
def move_up(self, inserted_idx):
if inserted_idx <= 1:
return False
parent_idx = inserted_idx // 2
if self.heap_array[inserted_idx] > self.heap_array[parent_idx]:
return True
else:
return False
def insert(self, data):
if len(self.heap_array) == 1:
self.heap_array.append(data)
return True
self.heap_array.append(data)
inserted_idx = len(self.heap_array) - 1
while self.move_up(inserted_idx):
parent_idx = inserted_idx // 2
self.heap_array[inserted_idx], self.heap_array[parent_idx] = self.heap_array[parent_idx], self.heap_array[inserted_idx]
inserted_idx = parent_idx
return True
heap = Heap(15)
heap.insert(10)
heap.insert(8)
heap.insert(5)
heap.insert(4)
heap.insert(20)
heap.heap_array
class Heap:
def __init__(self, data):
self.heap_array = list()
self.heap_array.append(None) # 인덱스 번호는 1번부터
self.heap_array.append(data)
def pop(self):
if len(self.heap_array) <= 1:
return None
returned_data = self.heap_array[1]
return returned_data
class Heap:
def __init__(self, data):
self.heap_array = list()
self.heap_array.append(None) # 인덱스 번호는 1번부터
self.heap_array.append(data)
def move_down(self, popped_idx):
left_child_popped_idx = popped_idx * 2
right_child_popped_idx = popped_idx * 2 + 1
if left_child_popped_idx >= len(self.heap_array):
return False
elif right_child_popped_idx >= len(self.heap_array):
if self.heap_array[popped_idx] < self.heap_array[left_child_popped_idx]:
return True
else:
return False
else:
if self.heap_array[left_child_popped_idx] > self.heap_array[right_child_popped_idx]:
if self.heap_array[popped_idx] < self.heap_array[left_child_popped_idx]:
return True
else:
return False
else:
if self.heap_array[popped_idx] < self.heap_array[right_child_popped_idx]:
return True
else:
return False
def pop(self):
if len(self.heap_array) <= 1:
return None
returned_data = self.heap_array[1]
self.heap_array[1] = self.heap_array[-1]
del self.heap_array[-1]
popped_idx = 1
while self.move_down(popped_idx):
left_child_popped_idx = popped_idx * 2
right_child_popped_idx = popped_idx * 2 + 1
if right_child_popped_idx >= len(self.heap_array):
self.heap_array[popped_idx], self.heap_array[left_child_popped_idx] = self.heap_array[left_child_popped_idx], self.heap_array[popped_idx]
poppoed_idx = left_child_popped_idx
else:
if self.heap_array[left_child_popped_idx] > self.heap_array[right_child_popped_idx]:
self.heap_array[popped_idx], self.heap_array[left_child_popped_idx] = self.heap_array[left_child_popped_idx], self.heap_array[popped_idx]
poppoed_idx = left_child_popped_idx
else:
self.heap_array[popped_idx], self.heap_array[right_child_popped_idx] = self.heap_array[right_child_popped_idx], self.heap_array[popped_idx]
poppoed_idx = right_child_popped_idx
return returned_data
def move_up(self, inserted_idx):
if inserted_idx <= 1:
return False
parent_idx = inserted_idx // 2
if self.heap_array[inserted_idx] > self.heap_array[parent_idx]:
return True
else:
return False
def insert(self, data):
if len(self.heap_array) == 1:
self.heap_array.append(data)
return True
self.heap_array.append(data)
inserted_idx = len(self.heap_array) - 1
while self.move_up(inserted_idx):
parent_idx = inserted_idx // 2
self.heap_array[inserted_idx], self.heap_array[parent_idx] = self.heap_array[parent_idx], self.heap_array[inserted_idx]
inserted_idx = parent_idx
return True
heap = Heap(15)
heap.insert(10)
heap.insert(8)
heap.insert(5)
heap.insert(4)
heap.insert(20)
heap.heap_array
heap.pop()
heap.heap_array