Итак, у меня есть ПОЛЬЗОВАТЕЛЬСКАЯ PriorityQueue (реализованная с использованием max-heap), содержащая песни.Каждая песня - это объект, который имеет несколько лайков, название песни и уникальный идентификатор.Приоритет каждой песни внутри PriorityQueue определяется как количество лайков, которые она имеет, и если две песни имеют одинаковое количество лайков, то сравнивается название песни.
Меня просят создать функцию «удалить», которая принимает в качестве аргумента идентификатор песни и удаляет его из PriorityQueue.Проблема в том, что мне нужно искать песню, которая имеет этот конкретный идентификатор, чтобы удалить его, что происходит в O (n), так как это линейный поиск.Я должен сделать функцию удаления в O (logn), но из того, что я прочитал, я понимаю, что невозможно искать в несортированном массиве меньше, чем O (n) ... Кто-то может предложить какие-нибудь идеи?
(намек на то, что нам, возможно, придется добавить некоторые вещи в функцию getMax (getMax возвращает корень PQ, который содержит самую популярную песню) и функцию вставки).