75 lines
2.3 KiB
Python
75 lines
2.3 KiB
Python
from cgitb import small
|
|
from heapq import heapify
|
|
import math
|
|
from multiprocessing.dummy import Array
|
|
|
|
from Node import Node, State
|
|
|
|
|
|
|
|
class Min_heap:
|
|
def __init__(self):
|
|
self.items = []
|
|
|
|
def parent(self,i):
|
|
return (i - 1) >> 1
|
|
|
|
def left(self,i):
|
|
return (i << 1) + 1
|
|
|
|
def right(self,i):
|
|
return (i << 1) + 2
|
|
|
|
def heapify(self, i):
|
|
l = self.left(i)
|
|
r = self.right(i)
|
|
if l < len(self.items) and self.items[l] < self.items[i]:
|
|
smallest = l
|
|
else:
|
|
smallest = i
|
|
if r < len(self.items) and self.items[r] < self.items[smallest]:
|
|
smallest = r
|
|
if smallest != i:
|
|
self.items[i], self.items[smallest] = self.items[smallest], self.items[i]
|
|
self.items[i].heap_index, self.items[smallest].heap_index = self.items[smallest].heap_index, self.items[i].heap_index
|
|
self.heapify(smallest)
|
|
|
|
def extract(self):
|
|
if len(self.items) < 1:
|
|
print("STOS PUSTY!")
|
|
return
|
|
min = self.items[0]
|
|
self.items[0] = self.items[len(self.items) - 1]
|
|
self.items.pop()
|
|
self.heapify(0)
|
|
return min
|
|
|
|
def decrese_key(self, index, item):
|
|
if item > self.items[index]:
|
|
print("Nowy klucz wiekszy od klucza aktualnego!")
|
|
return
|
|
self.items[index] = item
|
|
self.items[index].heap_index = index
|
|
while index > 0 and self.items[self.parent(index)] > self.items[index]:
|
|
self.items[index], self.items[self.parent(
|
|
index)] = self.items[self.parent(index)], self.items[index]
|
|
self.items[index].heap_index, self.items[self.parent(
|
|
index)].heap_index = self.items[self.parent(index)].heap_index, self.items[index].heap_index
|
|
index = self.parent(index)
|
|
|
|
def insert(self, item):
|
|
temp_node = Node(State(0,0,0),False)
|
|
temp_node.h_cost = math.inf
|
|
temp_node.heap_index = len(self.items) - 1
|
|
self.items.append(temp_node)
|
|
self.decrese_key(len(self.items) - 1, item)
|
|
|
|
def count(self):
|
|
return len(self.items)
|
|
|
|
def contains(self, item):
|
|
in_range = len(self.items) > item.heap_index
|
|
contains = False
|
|
if in_range:
|
|
contains = self.items[item.heap_index] is item
|
|
return in_range and contains |