Nano Hash - криптовалюты, майнинг, программирование

Объединение двух двоичных максимальных куч, в которых все элементы в одной куче больше, чем все элементы в другой?

Я пришел с этим вопросом интервью по программированию, и я не уверен, что мой ответ правильный. Я не смог найти правильный ответ на этот вопрос. Вот вопрос,

Пусть H1 и H2 — две (бинарные) max-кучи с n1 и n2 элементами соответственно. Если каждый элемент в H1 больше, чем каждый элемент в H2, разработайте алгоритм, который объединяет эти две кучи в одну (двоичную) максимальную кучу за время O(n2) (предположим, что и H1, и H2 достаточно велики, чтобы вместить n1 + n2). элементы)

Итак, я подумал, что, поскольку каждый элемент в H1 больше, чем каждый элемент в H2, мы можем хранить объединенную максимальную кучу в H1. Итак, все, что нам нужно сделать, это просто получить первый элемент из H2 в позиции 0 в массиве для H2, а затем вставить этот элемент в H1, добавить в конец массива H1, сделав его листом в H1. Мы можем непрерывно делать это для каждого элемента в H2. Я предполагаю, что как только мы начнем добавлять элементы из H2 в качестве дочерних элементов к элементам H2, нам придется начать проверять, меньше ли этот дочерний элемент, чем родитель, и если нет, мы меняем их местами. Я предполагаю, что, поскольку добавление элемента без вызова heapify и замена при необходимости даст нам сложность O (n2).

Итак, верно ли мое решение? Если нет, любая помощь будет высоко оценена. Пожалуйста, сообщите мне, если какая-либо часть моего решения неясна, чтобы я мог уточнить.

algorithm data-structures heap
22.10.2017

  • Такое ощущение, что это точно. Но я создал случай, когда вам нужно сделать более одного обмена. Учитывая, что H1 очень мал по сравнению с H2; это означает, что вам потребуется почти log(n2) свопов для одного элемента (H1:[100], H2[25 8 24 3 7 10 23 2 1 6 5 4 9 12 22]). Тем не менее, предполагается, что он встречается очень редко. Если мы сможем доказать, что такая ситуация будет встречаться пренебрежимо редко, то вы правы :) 22.10.2017
  • Так будет ли моя сложность для моего алгоритма на самом деле O (n2 + log (n2))? У меня нет большого опыта в вычислении сложности, поэтому я не уверен в этом. Будет ли это по-прежнему просто O (n2)? 22.10.2017
  • Честно говоря, я пока не уверен :( 22.10.2017
  • @ selecii44: количество возможных ошибок увеличивается с размером кучи, которую вы объединяете (т. Е. n2). Поиск узлов для обмена будет операцией O(n2), а их исправление потребует O(log n2) для каждого. Решение состоит в том, чтобы переставить всю кучу n2 за O(n2). Это делает всю операцию O(2*n2), которая считается O(n2). 24.10.2017

Ответы:


1

В общем случае вы не можете просто добавить H2 к H1, потому что, как было указано в комментариях, это может привести к недопустимой куче. Эта ситуация не является особенно редкой.

Например, представьте две максимальные кучи:

h1 = [100]
h2 = [6,3,5,1,2,4]

    h1        h2

   100        6
            3   5
           1 2 4

Если вы просто добавите h2 к h1, вы получите:

    100
  6    3
 5 1  2 4

Что явно неверно, потому что 4 является дочерним элементом 3.

Если h1=[100,98], может произойти то же самое:

       100
    99     6
   3  5  1   2
 4

Что вам нужно сделать, так это добавить h2 к h1, а затем запустить сокращенную build-heap, которая переупорядочивает элементы из h2, чтобы отразить их новые позиции в куче. Вы уже знаете, что все элементы, которые вы добавили из h2, меньше самого маленького элемента в h1, поэтому вам не нужно трогать какой-либо элемент из h1.

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

h1_length = h1.length
h2_length = h2.length
h1.array.append(h2.array)  // copies items from h2 to h1
// rearrange h2 items
start = h1_length + (h2_length/2)
for (item = start; item > h1_length; --item)
{
    i = item
    // This assumes that the root of the heap is at 0.
    // If the root is at 1, then the left child is at i*2
    while (i*2+1 < h1.length)
    {
        // get the largest child of this item
        leftChildIndex = i*2+1
        rightChildIndex = leftChildIndex + 1
        largestChildIndex = leftChildIndex
        if (rightChildIndex < h1.length &&
            h1.array[rightChildIndex] > h1.array[leftChildIndex)
        {
            largestChildIndex = rightChildIndex
        }
        // if the item is greater than or equal to its largest child,
        // then the item is where it belongs.
        if (h1.array[i] >= h1.array[largestChildIndex])
        {
            break;
        }
        // swap the item with its child, and check again
        swap(h1.array[i], h1.array[largestChildIndex])
        i = largestChildIndex
    }
}

Доказано, что алгоритм build-heap работает за O(n), где n — количество элементов в куче, которую вы создаете. Поскольку вы работаете только с h2.length элементами, это займет время O(h2.length).

23.10.2017
  • Что я вижу из вашего кода, его сложность составляет O (nlgn), предполагая, что n = h2 / 2. Я что-то упустил? 27.10.2017
  • @ seleciiii44: Как я указал в своем последнем абзаце, алгоритм build-heap — это O (n). См. stackoverflow.com/questions/9755721/ для объяснения. 27.10.2017
  • Спасибо, теперь я понял. 28.10.2017
    • Новые материалы
    Кластеризация: более глубокий взгляд
    Кластеризация — это метод обучения без учителя, в котором мы пытаемся найти группы в наборе данных на основе некоторых известных или неизвестных свойств, которые могут существовать. Независимо от..
    Как написать эффективное резюме
    Предложения по дизайну и макету, чтобы представить себя профессионально Вам не позвонили на собеседование после того, как вы несколько раз подали заявку на работу своей мечты? У вас может..
    Частный метод Python: улучшение инкапсуляции и безопасности
    Введение Python — универсальный и мощный язык программирования, известный своей простотой и удобством использования. Одной из ключевых особенностей, отличающих Python от других языков, является..
    Как я автоматизирую тестирование с помощью Jest
    Шутка для победы, когда дело касается автоматизации тестирования Одной очень важной частью разработки программного обеспечения является автоматизация тестирования, поскольку она создает..
    Работа с векторными символическими архитектурами, часть 4 (искусственный интеллект)
    Hyperseed: неконтролируемое обучение с векторными символическими архитектурами (arXiv) Автор: Евгений Осипов , Сачин Кахавала , Диланта Хапутантри , Тимал Кемпития , Дасвин Де Сильва ,..
    Понимание расстояния Вассерштейна: мощная метрика в машинном обучении
    В обширной области машинного обучения часто возникает необходимость сравнивать и измерять различия между распределениями вероятностей. Традиционные метрики расстояния, такие как евклидово..
    Обеспечение масштабируемости LLM: облачный анализ с помощью AWS Fargate и Copilot
    В динамичной области искусственного интеллекта все большее распространение получают модели больших языков (LLM). Они жизненно важны для различных приложений, таких как интеллектуальные..