- heap 정렬을 사용하기 위해서 heap을 먼저 구현함
class MaxHeap:
def __init__(self):
self.heap = []
self.heap.append(0)
def size(self):
return len(self.heap) - 1
def isEmpty(self):
return self.size == 0
def parent(self, i):
return self.heap[i // 2]
def Left(self, i):
return self.heap[i * 2]
def right(self, i):
return self.heap[i * 2 + 1]
def display(self, string="maxHeap"):
print(string, self.heap[1:]) # 1번에는 0이 삽입되어 있으니까 이를 이용한다.
def insert(self, data):
self.heap.append(data) # 제일 처음에 가장 작은 값이라고 가정하고 힙의 마지막에 삽임
index = self.size() # 삽입한 데이터 리스트의 인덱스를 반환
while index != 1 and data > self.parent(index): # 부모 노드 보다 새로 삽입한 data가 더 클때까지 반복
self.heap[index] = self.parent(index) # 부모가 더 작으니가 원래 부모를 끌어내린다.
index = index // 2 # 인덱스를 부모노드의 인덱스로 다시 만들어서 더 위의 부모와 비교하기 위해서 수행한다.
self.heap[index] = data # 위 조건을 만족하는 index에 데이터를 삽입한다.
def delete(self):
parent = 1
child = 2
if not self.isEmpty():
hroot = self.heap[1] # 반환할 root최대값
last = self.heap[self.size()] # 교환을 위해서 마지막 노들르 저장함
while child <= self.size(): # 마지막 인덱스 보다 작을 때까지 반복
if self.size() > child and self.Left(parent) < self.right(parent): # 부모 노드의 오른쪽 자식이 왼쪽 자식보다 크다면
child += 1 # 오른쪽 자식으로 바꾼다.
if last >= self.heap[child]: # 마지막 요소보다 작은 child를 찾았다면 last를 삽입할 위치를 찾음
break
self.heap[parent] = self.heap[child] # 부모 노드의 자리에 자식노드를 올림
parent = child # 부모를 자식으로 바꿈
child = child * 2 # 자식을 한단계 밑으로 내린다.
self.heap[parent] = last #마지막에 parent에 child가 삽입되고 끝났기 때문에 last를 parent의 위치에 삽입
self.heap.pop(-1)# 삭제 연산은 결국 마지막 요소를 지우는 연산임
return hroot#root를 반환hroot = self.heap[1] # 반환할 root최대값 최대값을 저장하는 root의 인덱스는 1이다
힙정렬을 위해서 maxheap을 먼저 구현함
def heapSorting(datalist):
maxHeap = MaxHeap()
for i in datalist:
maxHeap.insert(i)
for e in range(1, len(datalist) + 1): # range의 범위가 최대 -1이고 그리고 -1인덱스로 부터 시작하기 때문에 반드시 len(datalist)+1까지
datalist[-e] = maxHeap.delete()힙에 정렬할 요소를 다 넣고 오름차순으로 정렬하기 위해서 큰값부터 -1인덱스를 사용해서 삽입함 그리고 아까 실수한게 for 문에서 사용하는 인덱스로 습관적으로 i로 사용해서 계속 결과가 이상하게 나왔다.
# 힙정렬을 사용할때 이를 변경하기 위해서
def heapify(arr, arrlen, i):
largest = i
left = i * 2 + 1 # 원래 힙을 사용한것이 아니고 리스트를 사용했기 때문에 인덱스0번을 사용해서 왼쪽 자식이 i*2 +1이다
right = i * 2 + 2 # 인덱스 0 번을 사용한 list에서의 오른쪽 자식의 인덱스
if left < arrlen and arr[i] < arr[left]: largest = left # 왼쪽 자식이 더 크다면
if right < arrlen and arr[largest] < arr[right]: largest = right # 오른쪽 자식이 더 크다면
if largest != i: # 위의 if 문장이 실행되었다면
tmp = arr[i] # 부모와 자식간의 위치를 바꾼다.
arr[i] = arr[largest]
arr[largest] = tmp
heapify(arr, arrlen, largest) # 더 밑의 트리에서도 조건에 부합해야 하기 때문에 더 밑에 순환호출을 이용해서
# 자식을 최값으로 잡고 다시 호출한다.리스트를 다운힙연산을 해서 힙정렬을 실시하는 함수이다 .
if left < arrlen and arr[i] < arr[left]: largest = left # 왼쪽 자식이 더 크다면 if right < arrlen and arr[largest] < arr[right]: largest = right # 오른쪽 자식이 더 크다
if 문이 제일 중요한데 largest 에 현재 힙정렬을 시작하는 인덱스인 i를 부여하고 다시 이를 if 문에서 바꾼다
제일먼저 부모노드보다 왼쪽 자식 노드가 더 큰지에 대해서 계산하고 이후에 if문이 실행되어서 왼쪽 자식이 실행되든말든 그거보다 오른쪽이 더 크면 다시 largest를 오른쪽 자식으로 수정하는 과정을 거친다.
def heapSort(list):
length = len(list)
print("i=", 0, list)
for i in range(length // 2, -1, -1): # 완전트리에서 마지막 leaf는 이미 단일 노드로
# 이미 힙의 조건을 만족하기 때문에 제외하기 위해서 length//2
heapify(list, length, i)
print("i=", i, list)
print()
for i in range(length - 1, 0, -1): # list의 길이의 가장 마지막 인덱스 부터 차례대로 내려오면서 인덱스를 반환한다.
tmp = list[i] # 마지막 요소와 첫번째 요소를 교환한다.
list[i] = list[0]
list[0] = tmp
heapify(list, i, 0) # 함수를 호출하는데 arraylength 자리에 들어갈 파라미터에 i를 전달하는 것을 볼 수 있는데 이는
# 오름차순으로 정렬하기 위해서 아래의 뒤로 교환한 가장큰값을 정렬대상에서 제외하기 위해서다.
print("i=", i, list)
randlist = [int(random.randrange(1, 10)) for i in range(10)]
randlist2 = [int(random.randrange(1, 10)) for i in range(10)]
testlist = [5, 3, 8, 4, 9, 1, 6, 2, 7]
print("before sorting(heapSorting):", randlist)
heapSorting(randlist)
print("after sorting(heapSorting):", randlist)
print("result of sorting before:", testlist)
heapSort(testlist)
print("result of after sorting:", testlist)for i in range(length // 2, -1, -1): # 완전트리에서 마지막 leaf는 이미 단일 노드로
# 이미 힙의 조건을 만족하기 때문에 제외하기 위해서 length//2
heapify(list, length, i)
print("i=", i, list)
이 부분이 for문 범위가 완전이진트리에서 leaf를 제외하고 heapify연산을 실행할 수 있게 만들어준당
ㅎㅆㅆㅆㅆㅅ
코딩