VBNet - Форум - Алгоритм выборки двух наименьших

Вопрос: Алгоритм выборки двух наименьших Добавлено: 29.04.06 20:30

Автор вопроса: BUG(O)R | Web-сайт: hunger.ru | ICQ: 827887

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

Имеется массив структур:

Private Type TREE
    LeftPtr As Long
    RightPtr As Long
    Value As Long
    lpStr As String
End Type

Так вот суть в том, что нужно сделать выборку двух наименьших значений из массива этих структур при условии, что Value > 0, и всё бы ничего, казалось бы отсортировал один раз массив по значению Value, но кол-во элементов массива будет постоянно меняться а значение Value тех элементов, что уже были выбраны ранее будет обнуляться.

Кто может на пальцах, кто может кодом, кто как может объясните, как поступить?
Ответить

Ответы Всего ответов: 6

Номер ответа: 1 Автор ответа: HACKER Разработчик Offline Client Вопросов: 236 Ответов: 8362	Профиль \| \| #1	Добавлено: 29.04.06 22:29
	А зачем сортировать, можно... Dim MyTree as TREE Dim Max as Long Dim Index as Long, LastIndex as Long Max = 2147483647 '< проверь, я могу ошибаться 'Предположим что она заполнена... for i = 0 to ubound(MyTree) if MyTree.Value < Max Then Max = MyTree.Value LastIndex = Index Index = i Next i 'Теперь Index - индекс массива с наименшим MyTree.Value, ну а LastIndex второй по меншности эл. масс. p.s. не тестил... Ответить

Номер ответа: 2 Автор ответа: Sergey ICQ: 283551900 Вопросов: 1 Ответов: 74	Профиль \| \| #2	Добавлено: 30.04.06 14:08
	Вопрос интересный, редко такие попадаются. Для ответа информации мало в частности не хватает, как часто меняется Value и есть ограничения на изменение Value между выборками 2 элементов. 1в) поиск двух наименьших элементов в массиве время работы O(n)=n ( указан порядок) 2в) можно построит приоритетную очередь на бинарном дереве где отец меньше своих сыновей! (не помню название данного дерева). Так вот: выборка из него примерно O(n)=ln2(n) вставка элемента примерно O(n)=ln2(n) удаление элемента примерно O(n)=ln2(n) изменение приоритета элемента примерно O(n)=ln2(n) можно примерно прикинуть сколько надо времени на выборку и поддержание очереди между выборками и сравнить с другими вариантами прежде чем реализовывать. 3в) Если есть ограничение на изменение Value между выборками Тесть если Value может измениться максимум на 10 и Value = 41 то следующую выборку Value>31 далее Value>21 … Соответственно если нашли два элемента где Value<20 то нет смысл смотреть Value>21. :4в) создать массив(разряженный хуже 2 варианта) с индексам [Value] (если возможно примеру 0<=Value<1000) в массиве будут храниться списки. То есть в массиве под индексом 1 будет храниться все элементы с Value==1 Ответить

Номер ответа: 3 Автор ответа: HACKER Разработчик Offline Client Вопросов: 236 Ответов: 8362	Профиль \| \| #3	Добавлено: 30.04.06 18:30
	Не ты случайно автор девиза вбнета? Ответить

Номер ответа: 4 Автор ответа: Sergey ICQ: 283551900 Вопросов: 1 Ответов: 74	Профиль \| \| #4	Добавлено: 30.04.06 21:46
	Не ты случайно автор девиза вбнета? Какой девиз? Поправка: удаление элемента примерно O(n)=ln2(n)- верно для верхнего элемента, для всех остальных O(n)=n Ответить

Номер ответа: 5 Автор ответа: Fever Вопросов: 60 Ответов: 808	Профиль \| \| #5	Добавлено: 11.05.06 14:04
	ДЕВИЗ VBNET Все что вы и скали и не могли нигде найти В первый раз слышишь? НЕ ВЕРЮ!!! Ответить

Номер ответа: 6 Автор ответа: HACKER Разработчик Offline Client Вопросов: 236 Ответов: 8362	Профиль \| \| #6	Добавлено: 11.05.06 19:03
	да слышал... толку от девиза которые не оправдывается? А от "Мы не ищем лёгких путей" ешё куда не шло... хотя я был за обеими руками "Мы ИЩЕМ ТОЛЬКО сложные пути..." Ответить

Страница: 1 |