Реализуйте PriorityQueue, используя BinarySearchTree: Java

Question

Мне нужно «создать очередь приоритетов, реализуемую бинарным деревом поиска (BST)» для моих алгоритмов класса II.Тем не менее, я не уверен, как именно вы будете использовать бинарное дерево поиска в качестве приоритетной очереди.Может ли кто-нибудь уточнить, что означает, что задание просит меня сделать?

В качестве ссылки, вот методы, которые должен реализовать PriorityQueue:

add – adds a new item to the queue
peek – returns the head of the queue
remove – removes the head of the queue and returns it
search – returns the position of an element in the queue, or -1 if it is not found.
size – returns the total number of elements in the queue
inorder – returns an in-order, comma-separated string of every element in the queue
preorder – returns an pre-order, comma-separated string of every element in the queue
height – returns the height of the underlying BST

Заранее благодарю за любой совет!!

Answer 1

A Двоичное дерево поиска всегда упорядочено и всегда будет оставаться в порядке, если будут вставлены новые элементы.

Основным преимуществом деревьев двоичного поиска перед другими структурами данных является то, что связанные алгоритмы сортировки и алгоритмы поиска, такие как обход по порядку, могут быть очень эффективными.

Иэто ваша приоритетная очередь.В возможной реализации элементы с наименьшим приоритетом получат наибольшее число, а элементы с наивысшим приоритетом получат наименьшее число.Если эти элементы вставлены в BST и вы прочитали его inorder, то у вас есть порядок, в котором очередь должна обрабатываться.

Чтобы обработать очередь, вы «выталкиваете» первый элемент вдерево и все остальное будет автоматически упорядочено BST.

Единственное, о чем вам нужно позаботиться, это правильная вставка новых элементов в дерево и что произойдет, если удаляется первый элемент.

Ваши методы будут сопоставлены с операциями дерева, add вставит новый элемент в правильное место и при необходимости модифицирует дерево, например, size возвращает размер дерева, inorder будет проходить черезtree.

Надеюсь, это немного прояснило.

Answer 2

add peek remove - это стандартные методы для поиска BST

. Вы можете кэшировать размер в каждом узле, который будет текущим числом элементов в поддереве, корневым узлом которого является узел (или вдругими словами node.size = 1+ (node.right==null?0:node.right.size) + (node.left==null?0:node.left.size))

тогда поиск становится

int search(E el,Node n){
    if(n==null)return -1;//stop recursion && nullpointer
    int comp = el.compareTo(n.value);
    if(comp==0)return n.left==null?0:node.left.size;
    else if(comp<0){
        return search(el,node.left);
    }else{
        int res = search(el,node.right)
        return res<0?res:res+(n.left==null?0:node.left.size)+1;//pass through -1 unmodified
    }
}

Answer 3

A дерево двоичного поиска используется для эффективного сохранения элементов в отсортированном порядке.Если порядок сортировки основан на приоритете, то ваше двоичное дерево становится очередью приоритетов.Вы выбрасываете элемент с наивысшим приоритетом и вставляете новые элементы в соответствии с их приоритетом.

Отредактировано, чтобы добавить:

Это может помочь рассмотреть альтернативы - если вы использовалисвязанный список как ваша очередь, как вы узнали бы, куда вставить новый элемент, кроме как пройтись по всему списку, а это O (N) с наихудшим регистром N. Использование двоичного дерева решает эту проблему.