Assignment 2 - Build heap

Assignment 2 - Build heap

3주차에서 배운 내용을 토대로 과제를 진행하였고 그 중 1번째 문제는 heap을 생성하는 것이다.

HeapSort 알고리즘의 첫번째 스텝은 heap을 생성하는 것이며 이를 구현하여야 한다. min-heap으로 정렬을 완료해야 하며 이에 대한 인자들은 다음과 같다.

input format :
n (heap의 크기)
a1 a2 a3 ... ai (원소들)

output format :
m (총 교환 횟수)
ai aj (각 교환한 원소들의 인덱스)
ai aj
ai aj
...

예시로 넘어가서 Sample 1을 보면 n은 5이고 이들의 배열에는 5, 4, 3, 2, 1이 들어선 것을 알 수 있다. 이를 min-heap으로 완성시키기 위해서는 3번(m)의 교환이 필요하며 이 때 교환되는 원소들의 인덱스들이 나열되는 것을 알 수 있다. 0-base array인 것을 유의해야 한다.

# python3
class HeapBuilder:
  def __init__(self):
    self._swaps = []
    self._data = []

  def ReadData(self):
    n = int(input())
    self._data = [int(s) for s in input().split()]
    assert n == len(self._data)

  def WriteResponse(self):
    print(len(self._swaps))
    for swap in self._swaps:
      print(swap[0], swap[1])

  def GenerateSwaps(self):
    # The following naive implementation just sorts     # the given sequence using selection sort algorithm    # and saves the resulting sequence of swaps.    # This turns the given array into a heap,     # but in the worst case gives a quadratic number of swaps.    #    # TODO: replace by a more efficient implementation    for i in range(len(self._data)):
      for j in range(i + 1, len(self._data)):
        if self._data[i] > self._data[j]:
          self._swaps.append((i, j))
          self._data[i], self._data[j] = self._data[j], self._data[i]

  def Solve(self):
    self.ReadData()
    self.GenerateSwaps()
    self.WriteResponse()

if __name__ == '__main__':
    heap_builder = HeapBuilder()
    heap_builder.Solve()

우선 기본 코드는 위와 같았다. HeapBuilder라는 class를 선언하고 그 내부에 인자는 swaps과 data를 가져가고 ReadData, WriteResponse, GenerateSwaps, Solve 함수들을 가지게 된다. 이때 GenerateSwaps를 수정하여 제 기능을 하도록 구현하면 된다.

# python3

class HeapBuilder:
  def __init__(self):
    self._swaps = []
    self._data = []

  def ReadData(self):
    n = int(input())
    self._data = [int(s) for s in input().split()]
    assert n == len(self._data)

  def WriteResponse(self):
    print(len(self._swaps))
    for swap in self._swaps:
      print(swap[0], swap[1])

  def HeapSortEven(self, i):
    if self._data[i] > self._data[2 * i + 1] or self._data[i] > self._data[2 * i + 2]:
      if self._data[2 * i + 1] < self._data[2 * i + 2]:
        self._data[i], self._data[2 * i + 1] = self._data[2 * i + 1], self._data[i]
        self._swaps.append([i, 2*i+1])
        if 2*i+1 < len(self._data)//2-1:
          HeapBuilder.HeapSortEven(self, 2*i+1)
        elif 2*i+1 == len(self._data)//2-1 and len(self._data) % 2 == 0:
          HeapBuilder.HeapSortOdd(self, 2*i+1)
        elif 2*i+1 == len(self._data)//2-1 and len(self._data) % 2 == 1:
          HeapBuilder.HeapSortEven(self, 2*i+1)
      else:
        self._data[i], self._data[2 * i + 2] = self._data[2 * i + 2], self._data[i]
        self._swaps.append([i, 2*i+2])
        if 2*i+2 < len(self._data)//2-1:
          HeapBuilder.HeapSortEven(self, 2*i+2)
        elif 2*i+2 == len(self._data)//2-1 and len(self._data) % 2 == 0:
          HeapBuilder.HeapSortOdd(self, 2*i+2)
        elif 2*i+2 == len(self._data)//2-1 and len(self._data) % 2 == 1:
          HeapBuilder.HeapSortEven(self, 2*i+2)

  def HeapSortOdd(self, i):
    if self._data[i] > self._data[2 * i + 1]:
      self._data[i], self._data[2 * i + 1] = self._data[2 * i + 1], self._data[i]
      self._swaps.append([i, 2*i+1])

  def GenerateSwaps(self):
    # The following naive implementation just sorts     # the given sequence using selection sort algorithm    # and saves the resulting sequence of swaps.    # This turns the given array into a heap,     # but in the worst case gives a quadratic number of swaps.    #    # TODO: replace by a more efficient implementation    if len(self._data) % 2 == 0:
      i = len(self._data)//2-1      HeapBuilder.HeapSortOdd(self, i)
      for i in range(len(self._data)//2-2, -1, -1):
        HeapBuilder.HeapSortEven(self, i)

    else:
      for i in range(len(self._data)//2-1, -1, -1):
        HeapBuilder.HeapSortEven(self, i)

  def Solve(self):
    self.ReadData()
    self.GenerateSwaps()
    self.WriteResponse()


if __name__ == '__main__':
    heap_builder = HeapBuilder()
    heap_builder.Solve()

일단 GenerateSwaps내부에서만 구성하기에는 뭔가 부족했다. 따라서 HeapSortEven과 HeapSortOdd를 추가하였으며 이들은 같은 기능이나 자식노드가 1개인지 2개인지에 따라 구분된 역할만 하도록 하였다.

약간 간결하게 짜지는 못했지만 일단 시험셋은 모두 통과하였기에 이 상태로 넘기게 되었다. GenerateSwaps에서는 입력한 heap이 홀수개인지 짝수개인지를 먼저 판별하고 그에 따라 for문으로 들어가며 이후 HeapSortEven이나 HeapSortOdd를 적절히 선정하여 작동하도록 되어있다. 특히 Heap Sort의 특성대로 아래노드로부터 윗노드로 전달이 되면서 정렬이 되어야 하기에 for문의 순서도 뒤에서부터 1씩 감소하며 index를 바꾸었다. 게다가 재귀함수를 통해 해당 노드에서 바꾼 값이 하위단까지 정상적으로 도달 할 수 있도록 하였다.

ps. Assignment 1과 달리 이번 과제는 test set를 거의 주지않아 여러번 제출해보고 feedback을 받아서 좀 힘들었다.