Queue sorting in python AI

I’m trying to implement Best First Algorithm as a solution to a building evacuation project.

The building has 4 floors, the roof, and floor 0.
We’re using functions like go_to_roof for the movement of the elevator in each repetition until the goal has been met.

The goal is for the elevator to stay on the roof, and for all the residents to have evacuated.

The main looks like this

def main():

initial_state = [0, 9, 4, 12, 7, 0]
goal = [5, 0, 0, 0, 0, 0]


""" ----------------------------------------------------------------------------
**** starting search
**** έναρξη αναζήτησης
"""

print('____BEGIN__SEARCHING____')
method = input("Enter the search method (BFS / DFS / BEFS): ").upper()
if method not in ['BFS', 'DFS', 'BEFS']:
    print("Error: Invalid method.")
    return

find_solution(make_front(initial_state), make_queue(initial_state), [], goal, method)

So basically, using BFS, DFS and Best First I’m supposed to traverse all situations generated by each one. When i run BFS i get:
GOAL_FOUND
[5, 0, 0, 0, 0, 0]
[[0, 9, 4, 12, 7, 0], [4, 9, 4, 12, 0, 7], [1, 8, 4, 12, 0, 8], [5, 8, 4, 12, 0, 0], [3, 8, 4, 4, 0, 8], [5, 8, 4, 4, 0, 0], [3, 8, 4, 0, 0, 4], [2, 8, 0, 0, 0, 8], [5, 8, 0, 0, 0, 0], [1, 0, 0, 0, 0, 8], [5, 0, 0, 0, 0, 0]]

For Best First, I have to use an heuristic criterion.

When using best first you’re supposed to add the children at the front of the path, hence the insert(0, child) and then sort them based on an heuristic criterion.

As the criterion, I’ve chosen the least sum of states[1:5]
State[-1] is the floor of the elevator at all times, state[1] – state[5] are the number of residents on each floor and on the roof.

For example, a state looks like this

def go_to_floor1(state):
    if state[-1]<8 and state[1]>0:
        if state[1]>8-state[-1]:
            new_state = [1] + [state[1] + state[-1] - 8] + [state[2]] + [state[3]] + [state[4]] + [8]
        else:
            new_state = [1] + [0] + [state[2]] + [state[3]] + [state[4]] + [state[1] + state[-1]]
        return new_state

Hence, the heuristic criterion is this:

def sum_state(state):
        return sum(state[1:5])

For the front I’ll include here the ones for BFS and DFS so you can understand what i’m going for

def expand_front(front, method):  
    if method=='DFS':        
        if front:
            print("Front:")
            print(front)
            node=front.pop(0)
            for child in find_children(node):     
                front.insert(0,child)
                
    elif method=='BFS':
        if front:
            print("Front:")
            print(front)
            node=front.pop(0)
            for child in find_children(node):     
                front.append(child)

    elif method == 'BEFS':
        if front:
            print("Front:")
            print(front)
            node = front.pop(0)
            for child in find_children(node):
                front.insert(0,child)
                front.sort(key=sum_state) 
                
    return front

Finally, for queue, I don’t know where I’m supposed to do the sorting

def extend_queue(queue, method):
    if method == 'DFS':
        print("Queue:")
        print(queue)
        node = queue.pop(0)
        queue_copy = copy.deepcopy(queue)
        children = find_children(node[-1])
        for child in children:
            path = copy.deepcopy(node)
            path.append(child)
            queue_copy.insert(0, path)

    elif method == 'BFS':
        print("Queue:")
        print(queue)
        node = queue.pop(0)
        queue_copy = copy.deepcopy(queue)
        children = find_children(node[-1])
        for child in children:
            path = copy.deepcopy(node)
            path.append(child)
            queue_copy.append(path)

    elif method == 'BEFS':
        print("Queue:")
        print(queue)
        node = queue.pop(0)
        queue_copy = copy.deepcopy(queue)
        children = find_children(node[-1])
        for child in children:
            path = copy.deepcopy(node)
            path.append(child)
            queue_copy.append(path)
            queue_copy.sort(key=sum_state)
    
    return queue_copy

So, im almost certain my sort implementation on the expand front is correct, but i dont know how to handle the queue