heapをPythonで

heapをPythonで

heapの実装を一からPythonでやってみたよ Classを使ったものと使ってないものの二つ。

Classなしのもの

# heap_last_index = 0

def insert(heap,obj):
  # heap_last_index += 1
  heap.append(obj)
  # print(heap)
  i = len(heap)-1
  while i > 0:
    if heap[(i-1)//2] > heap[i]: # chech the parents nodes
      heap[(i-1)//2] , heap[i] = heap[i] , heap[(i-1)//2]
      i = (i-1)//2
    else:
      return


def deletemin(heap):
  obj = heap[0]
  heap[0] = heap.pop()
  print(obj)
  # heap_last_index -= 1

  i = 0
  while i < (len(heap)-1)//2:
    if heap[i] > heap[i*2+1]:
      if heap[i*2+2] < heap[i*2+1]:
        heap[i],heap[i*2+2] = heap[i*2+2],heap[i]
        i = i*2+2
      else:
        heap[i],heap[i*2+1] = heap[i*2+1],heap[i]
        i = i*2+1
    elif heap[i] > heap[i*2+2]:
      heap[i],heap[i*2+2] = heap[i*2+2],heap[i]
      i = i*2+2
    else:
      return


heap = []

insert(heap,1)
insert(heap,2)
insert(heap,3)
insert(heap,6)
insert(heap,3)
insert(heap,3)
deletemin(heap)
deletemin(heap)
print(heap)

Classありのもの

class heap:
  def __init__(self, n):
    inf = float("INF")
    self.data = [inf for _ in range(n)]
    self.last = 0

  def insert(self,obj):
    self.last += 1 
    self.data[self.last] = obj
    
    i = self.last
    while i>0:
      if self.data[(i-1)//2] > self.data[i]:
        self.data[(i-1)//2] , self.data[i] = self.data[i] , self.data[(i-1)//2]
        i = (i-1)//2
      else:
        return 
  
  def print_lis(self):
    print(self.data)

  def deletemin(self):
    obj = self.data[0]
    self.data[0] = self.data[self.last]
    # print(obj)
    self.last -= 1

    i = 0
    while i < (self.last-1)//2:
      if self.data[i] > self.data[i*2-1]:
        if self.data[i*2+2] < self.data[i*2+1]:
          self.data[i] , self.data[i*2+2] = self.data[i*2+2] , self.data[i]
          i = i*2+2
        else:
          self.data[i] , self.data[i*2+1] = self.data[i*2+1] , self.data[i]
          i = i*2+1
      elif self.data[i] > self.data[i*2+2]:
        self.data[i] , self.data[i*2+2] = self.data[i*2+2] , self.data[i]
        i = i*2+2
      else:
        break
    return obj
h = heap(10)
h.insert(103)
h.insert(110)
h.insert(310)
h.insert(120)
print(h.deletemin())
h.print_lis()