Самый быстрый алгоритм поиска второго по величине элемента в Max Heap (с дубликатами) - PullRequest
Новая
       20

Самый быстрый алгоритм поиска второго по величине элемента в Max Heap (с дубликатами)

0 голосов
/ 15 декабря 2018

Если у вас есть максимальная куча, содержащая n целых чисел, какой будет самый эффективный способ найти второй по величине элемент?Куча может содержать дубликаты, поэтому куча с n-1 max значениями и 1 другим значением будет возвращать другое значение

Например, куча, содержащая числа: 

4,4,4,4,4,4,4,3,4

вернет значение 3.

Есть ли способ сделать это быстрее, чем O(n) время выполнения?

1 Ответ

0 голосов
/ 15 декабря 2018

Нет способа сделать это с лучшей временной сложностью, чем O (n) .С данными примера, которые вы даете (4,4,4,4,4,4,4,3,4), куча может, например, быть одной из этих двух: 

             4                      4
           /   \                  /   \
         4       4              4       4
        / \     / \            / \     / \
       4   4   4   4          4   4   3   4
      / \                    / \
     4   3                  4   4

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

Если вы готовы использовать слегка альтернативную структуру данных, то это можно сделать в O (1) :

Сохранять уникальные значения в куче.Используйте хэш-карту для хранения информации о добавленном вами значении.В простом случае эта «информация» может быть счетчиком событий.Поэтому в следующий раз, когда вы захотите вставить в структуру то же самое значение , вы обнаружите, что оно уже есть в хэш-карте, и только увеличите соответствующий счетчик вхождений, а не коснетесь кучи.

Для приведенного выше примера структура данных будет выглядеть следующим образом: 

    heap              hashmap
                    key | value (=frequency)
       4           -----+-------------------
      /              4  |  8
     3               3  |  1

Если ваши элементы данных представляют собой сложные структуры, объединяющие ключ с некоторыми связанными данными (свойствами), то вы все равнохранить только ключи в куче без дубликатов.Тогда в хэш-карте будет указан не счетчик для каждого ключа, а массив фактических элементов данных, которые совместно используют тот же ключ.

Итак, для ясности, реализация операций, таких как вставка, удаление и поиск, должнабыть настроеннымВот некоторый псевдокод, предполагающий существование двух переменных heap и hashmap, которые имеют соответствующее поведение: 

function insert(element):
    key = element.key
    if key not in hashmap:
        hashmap.set(key, new Array)
        heap.insert(key)
    arr = hashmap.get(key) # get a reference to the array
    arr.append(element) # add element to array, affecting the hashmap-stored value

function extract(): # remove max element
    if heap.size() == 0:
        return # No more data
    key = heap.peek() # look at root value
    arr = hashmap.get(key) # get a reference to the array
    element = arr.pop() # extract from array, affecting the hashmap-stored value
    if arr.length() == 0:
        heap.extract()
        hashmap.delete(key)
    return element

function peek(): # return element with max value
    if heap.size() == 0:
        return # No more data
    key = heap.peek() # look at root value
    arr = hashmap.get(key)
    element = arr[-1] # last element in array
    return element

Вы можете получить наибольшее значение, которое меньше максимального значения, следующим образом: 

key = max(heap.root.children())

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

...