Фибоначчиева куча
Поделись знанием:
– Ну, мой друг, завтра мы едем, наконец, – сказал он ему однажды, закрывая глаза, перебирая пальцами его локоть и таким тоном, как будто то, что он говорил, было давным давно решено между ними и не могло быть решено иначе.
– Завтра мы едем, я тебе даю место в своей коляске. Я очень рад. Здесь у нас всё важное покончено. А мне уж давно бы надо. Вот я получил от канцлера. Я его просил о тебе, и ты зачислен в дипломатический корпус и сделан камер юнкером. Теперь дипломатическая дорога тебе открыта.
Несмотря на всю силу тона усталости и уверенности, с которой произнесены были эти слова, Пьер, так долго думавший о своей карьере, хотел было возражать. Но князь Василий перебил его тем воркующим, басистым тоном, который исключал возможность перебить его речь и который употреблялся им в случае необходимости крайнего убеждения.
– Mais, mon cher, [Но, мой милый,] я это сделал для себя, для своей совести, и меня благодарить нечего. Никогда никто не жаловался, что его слишком любили; а потом, ты свободен, хоть завтра брось. Вот ты всё сам в Петербурге увидишь. И тебе давно пора удалиться от этих ужасных воспоминаний. – Князь Василий вздохнул. – Так так, моя душа. А мой камердинер пускай в твоей коляске едет. Ах да, я было и забыл, – прибавил еще князь Василий, – ты знаешь, mon cher, что у нас были счеты с покойным, так с рязанского я получил и оставлю: тебе не нужно. Мы с тобою сочтемся.
То, что князь Василий называл с «рязанского», было несколько тысяч оброка, которые князь Василий оставил у себя.
В Петербурге, так же как и в Москве, атмосфера нежных, любящих людей окружила Пьера. Он не мог отказаться от места или, скорее, звания (потому что он ничего не делал), которое доставил ему князь Василий, а знакомств, зовов и общественных занятий было столько, что Пьер еще больше, чем в Москве, испытывал чувство отуманенности, торопливости и всё наступающего, но не совершающегося какого то блага.
Из прежнего его холостого общества многих не было в Петербурге. Гвардия ушла в поход. Долохов был разжалован, Анатоль находился в армии, в провинции, князь Андрей был за границей, и потому Пьеру не удавалось ни проводить ночей, как он прежде любил проводить их, ни отводить изредка душу в дружеской беседе с старшим уважаемым другом. Всё время его проходило на обедах, балах и преимущественно у князя Василия – в обществе толстой княгини, его жены, и красавицы Элен.
Анна Павловна Шерер, так же как и другие, выказала Пьеру перемену, происшедшую в общественном взгляде на него.
Прежде Пьер в присутствии Анны Павловны постоянно чувствовал, что то, что он говорит, неприлично, бестактно, не то, что нужно; что речи его, кажущиеся ему умными, пока он готовит их в своем воображении, делаются глупыми, как скоро он громко выговорит, и что, напротив, самые тупые речи Ипполита выходят умными и милыми. Теперь всё, что ни говорил он, всё выходило charmant [очаровательно]. Ежели даже Анна Павловна не говорила этого, то он видел, что ей хотелось это сказать, и она только, в уважение его скромности, воздерживалась от этого.
В начале зимы с 1805 на 1806 год Пьер получил от Анны Павловны обычную розовую записку с приглашением, в котором было прибавлено: «Vous trouverez chez moi la belle Helene, qu'on ne se lasse jamais de voir». [у меня будет прекрасная Элен, на которую никогда не устанешь любоваться.]
Читая это место, Пьер в первый раз почувствовал, что между ним и Элен образовалась какая то связь, признаваемая другими людьми, и эта мысль в одно и то же время и испугала его, как будто на него накладывалось обязательство, которое он не мог сдержать, и вместе понравилась ему, как забавное предположение.
Вечер Анны Павловны был такой же, как и первый, только новинкой, которою угощала Анна Павловна своих гостей, был теперь не Мортемар, а дипломат, приехавший из Берлина и привезший самые свежие подробности о пребывании государя Александра в Потсдаме и о том, как два высочайшие друга поклялись там в неразрывном союзе отстаивать правое дело против врага человеческого рода. Пьер был принят Анной Павловной с оттенком грусти, относившейся, очевидно, к свежей потере, постигшей молодого человека, к смерти графа Безухого (все постоянно считали долгом уверять Пьера, что он очень огорчен кончиною отца, которого он почти не знал), – и грусти точно такой же, как и та высочайшая грусть, которая выражалась при упоминаниях об августейшей императрице Марии Феодоровне. Пьер почувствовал себя польщенным этим. Анна Павловна с своим обычным искусством устроила кружки своей гостиной. Большой кружок, где были князь Василий и генералы, пользовался дипломатом. Другой кружок был у чайного столика. Пьер хотел присоединиться к первому, но Анна Павловна, находившаяся в раздраженном состоянии полководца на поле битвы, когда приходят тысячи новых блестящих мыслей, которые едва успеваешь приводить в исполнение, Анна Павловна, увидев Пьера, тронула его пальцем за рукав.
– Attendez, j'ai des vues sur vous pour ce soir. [У меня есть на вас виды в этот вечер.] Она взглянула на Элен и улыбнулась ей. – Ma bonne Helene, il faut, que vous soyez charitable pour ma рauvre tante, qui a une adoration pour vous. Allez lui tenir compagnie pour 10 minutes. [Моя милая Элен, надо, чтобы вы были сострадательны к моей бедной тетке, которая питает к вам обожание. Побудьте с ней минут 10.] А чтоб вам не очень скучно было, вот вам милый граф, который не откажется за вами следовать.
Красавица направилась к тетушке, но Пьера Анна Павловна еще удержала подле себя, показывая вид, как будто ей надо сделать еще последнее необходимое распоряжение.
– Не правда ли, она восхитительна? – сказала она Пьеру, указывая на отплывающую величавую красавицу. – Et quelle tenue! [И как держит себя!] Для такой молодой девушки и такой такт, такое мастерское уменье держать себя! Это происходит от сердца! Счастлив будет тот, чьей она будет! С нею самый несветский муж будет невольно занимать самое блестящее место в свете. Не правда ли? Я только хотела знать ваше мнение, – и Анна Павловна отпустила Пьера.
Пьер с искренностью отвечал Анне Павловне утвердительно на вопрос ее об искусстве Элен держать себя. Ежели он когда нибудь думал об Элен, то думал именно о ее красоте и о том не обыкновенном ее спокойном уменьи быть молчаливо достойною в свете.
Фибоначчиева куча (англ. Fibonacci heap) — структура данных, представляющая собой набор деревьев, упорядоченных в соответствии со свойством неубывающей пирамиды. Фибоначчиевы кучи были введены Майклом Фредманом и Робертом Тарьяном в 1984 году.
Структура является реализацией абстрактного типа данных «Очередь с приоритетом», и замечательна тем, что операции, в которых не требуется удаление, имеют амортизированное время работы, равное <math>O(1)</math> (для двоичной кучи и биномиальной кучи амортизационное время работы равно <math>O(\log n)</math>).
Кроме стандартных операций INSERT, MIN, EXTRACT-MIN, фибоначчиева куча позволяет за время <math>O(1)</math> выполнять операцию UNION слияния двух куч.
Содержание
Структура
- Фибоначчиева куча <math>H</math> представляет собой набор деревьев.
- Каждое дерево в <math>H</math> подчиняется свойству неубывающей пирамиды (англ. min-heap property): ключ узла не меньше ключа его родительского узла.
- Каждый узел <math>x</math> в <math>H</math> содержит следующие указатели и поля:
- <math>key[x]</math> — поле, в котором хранится ключ;
- <math>p[x]</math> — указатель на родительский узел;
- <math>child[x]</math> — указатель на один из дочерних узлов;
- <math>left[x]</math> — указатель на левый сестринский узел;
- <math>right[x]</math> — указатель на правый сестринский узел;
- <math>degree[x]</math> — поле, в котором хранится количество дочерних узлов;
- <math>mark[x]</math> — логическое значение, которое указывает, были ли потери узлом <math>x</math> дочерних узлов, начиная с момента, когда <math>x</math> стал дочерним узлом какого-то другого узла.
- Дочерние узлы <math>x</math> объединены при помощи указателей <math>left</math> и <math>right</math> в один циклический дважды связанный список дочерних узлов (англ. child list) <math>x</math>.
- Корни всех деревьев в <math>H</math> связаны при помощи указателей <math>left</math> и <math>right</math> в циклический дважды связанный список корней (англ. root list).
- Обращение к <math>H</math> выполняется посредством указателя <math>min[H]</math> на корень дерева с минимальным ключом. Этот узел называется минимальным узлом (англ. minimum node) <math>H</math>.
- Текущее количество узлов в <math>H</math> хранится в <math>n[H]</math>.
Операции
Создание новой фибоначчиевой кучи
Процедура Make_Fib_Heap возвращает объект фибоначчиевой кучи <math>H</math>, <math>n[H] = 0</math> и <math>min[H]</math> = NULL. Деревьев в <math>H</math> нет.
Амортизированная стоимость процедуры равна её фактической стоимости <math>O(1)</math>.
Вставка узла
Fib_Heap_Insert<math>(H,x)</math> 1 <math>degree[x]</math> ← 0 2 <math>p[x]</math> ← NULL 3 <math>child[x]</math> ← NULL 4 <math>left[x]</math> ← <math>x</math> 5 <math>right[x]</math> ← <math>x</math> 6 <math>mark[x]</math> ← FALSE 7 Присоединение списка корней, содержащего <math>x</math>, к списку корней <math>H</math> 8 if <math>min[H]</math> = NULL или <math>key[x] < key[min[H]]</math> 9 then <math>min[H]</math> ← <math>x</math> 10 <math>n[H]</math> ← <math>n[H]</math> + 1
Амортизированная стоимость процедуры равна её фактической стоимости <math>O(1)</math>.
Поиск минимального узла
Процедура Fib_Heap_Minimum возвращает указатель <math>min[H]</math>.
Амортизированная стоимость процедуры равна её фактической стоимости <math>O(1)</math>.
Объединение двух фибоначчиевых куч
Fib_Heap_Union<math>(H_1,H_2)</math> 1 <math>H</math> ← Make_Fib_Heap() 2 <math>min[H]</math> ← <math>min[H_1]</math> 3 Добавление списка корней <math>H_2</math> к списку корней <math>H</math> 4 if (<math>min[H_1]</math> = NULL) или (<math>min[H_2]</math> ≠ NULL и <math>key[min[H_2]]</math> < <math>key[min[H_1]]</math>) 5 then <math>min[H]</math> ← <math>min[H_2]</math> 6 <math>n[H]</math> ← <math>n[H_1] + n[H_2]</math> 7 Освобождение объектов <math>H_1</math> и <math>H_2</math> 8 return <math>H</math>
Амортизированная стоимость процедуры равна её фактической стоимости <math>O(1)</math>.
Извлечение минимального узла
Fib_Heap_Extract_Min<math>(H)</math> 1 <math>z</math> ← <math>min[H]</math> 2 if <math>z</math> ≠ NULL 3 then for для каждого дочернего по отношению к <math>z</math> узла <math>x</math> 4 do Добавить <math>x</math> в список корней <math>H</math> 5 <math>p[x]</math> ← NULL 6 Удалить <math>z</math> из списка корней <math>H</math> 7 if <math>z</math> = <math>right[z]</math> 8 then <math>min[H]</math> ← NULL 9 else <math>min[H]</math> ← <math>right[z]</math> 10 Consolidate<math>(H)</math> 11 <math>n[H]</math> ← <math>n[H] - 1</math> 12 return <math>z</math>
На одном из этапов операции извлечения минимального узла выполняется уплотнение (англ. consolidating) списка корней <math>H</math>. Для этого используется вспомогательная процедура Consolidate. Эта процедура использует вспомогательный массив <math>A[0..D[n[H]]]</math>. Если <math>A[i] = y</math>, то <math>y</math> в настоящий момент является корнем со степенью <math>degree[y] = i</math>.
Consolidate<math>(H)</math> 1 for <math>i</math> ← 0 to <math>D(n[H])</math> 2 do <math>A[i]</math> ← NULL 3 for для каждого узла <math>w</math> в списке корней <math>H</math> 4 do <math>x</math> ← <math>w</math> 5 <math>d</math> ← <math>degree[x]</math> 6 while <math>A[d]</math> ≠ NULL 7 do <math>y</math> ← <math>A[d]</math> //Узел с той же степенью, что и у <math>x</math> 8 if <math>key[x] > key[y]</math> 9 then обменять <math>x</math> ↔ <math>y</math> 10 Fib_Heap_Link<math>(H,y,x)</math> 11 <math>A[d]</math> ← NULL 12 <math>d</math> ← <math>d + 1</math> 13 <math>A[d]</math> ← <math>x</math> 14 <math>min[H]</math> ← NULL 15 for <math>i</math> ← 0 to <math>D(n[H])</math> 16 do if <math>A[i]</math> ≠ NULL 17 then Добавить <math>A[i]</math> в список корней <math>H</math> 18 if <math>min[H]</math> = NULL или <math>key[A[i]] < key[min[H]]</math> 19 then <math>min[H]</math> ← <math>A[i]</math>
Fib_Heap_Link<math>(H,y,x)</math> 1 Удалить <math>y</math> из списка корней <math>H</math> 2 Сделать <math>y</math> дочерним узлом <math>x</math>, увеличить <math>degree[x]</math> 3 <math>mark[y]</math> ← FALSE
Амортизированная стоимость извлечения минимального узла равна <math>O(\log n)</math>.
Уменьшение ключа
Fib_Heap_Decrease_Key<math>(H,x,k)</math> 1 if <math>k > key[x]</math> 2 then error «Новый ключ больше текущего» 3 <math>key[x]</math> ← <math>k</math> 4 <math>y</math> ← <math>p[x]</math> 5 if <math>y</math> ≠ NULL и <math>key[x] < key[y]</math> 6 then Cut<math>(H,x,y)</math> 7 Cascading_Cut<math>(H,y)</math> 8 if <math>key[x] < key[min[H]]</math> 9 then <math>min[H]</math> ← <math>x</math>
Cut<math>(H,x,y)</math> 1 Удаление <math>x</math> из списка дочерних узлов <math>y</math>, уменьшение <math>degree[y]</math> 2 Добавление <math>x</math> в список корней <math>H</math> 3 <math>p[x]</math> ← NULL 4 <math>mark[x]</math> ← FALSE
Cascading_Cut<math>(H,y)</math> 1 <math>z</math> ← <math>p[y]</math> 2 if <math>z</math> ≠ NULL 3 then if <math>mark[y]</math> = FALSE 4 then <math>mark[y]</math> ← TRUE 5 else Cut<math>(H,y,z)</math> 6 Cascading_Cut<math>(H,z)</math>
Амортизированная стоимость уменьшения ключа не превышает <math>O(1)</math>.
Удаление узла
Fib_Heap_Delete<math>(H,x)</math> 1 Fib_Heap_Decrease_Key<math>(H,x,-</math>∞<math>)</math> 2 Fib_Heap_Extract_Min<math>(H)</math>
Амортизированное время работы процедуры равно <math>O(\log n)</math>.
См. также
Напишите отзыв о статье "Фибоначчиева куча"
Ссылки
- [www.cs.yorku.ca/~aaw/Jason/FibonacciHeapAnimation.html Визуализатор] (англ.)
- [resnet.uoregon.edu/~gurney_j/jmpc/fib.html Реализация структуры на C] (англ.)
- Владимир Алексеев, Владимир Таланов, [www.intuit.ru/studies/courses/100/100/lecture/1541?page=2 Лекция 7: Биномиальные и фибоначчиевы кучи] // "Структуры данных и модели вычислений", 26.09.2006, intuit.ru
Литература
- Томас Х. Кормен и др. Алгоритмы: построение и анализ. — 2-е изд. — М.: Издательский дом «Вильямс», 2007. — С. 1296. — ISBN 5-8459-0857-4.
- Mehlhorn, Kurt, Sanders, Peter. 6.2.2 Fibonacci Heaps // Algorithms and Data Structures: The Basic Toolbox. — Springer, 2008. — 300 с. — ISBN 978-3-540-77978-0.
Отрывок, характеризующий Фибоначчиева куча
«Vous savez, que je suis accable d'affaires et que ce n'est que par pure charite, que je m'occupe de vous, et puis vous savez bien, que ce que je vous propose est la seule chose faisable». [Ты знаешь, я завален делами; но было бы безжалостно покинуть тебя так; разумеется, что я тебе говорю, есть единственно возможное.]– Ну, мой друг, завтра мы едем, наконец, – сказал он ему однажды, закрывая глаза, перебирая пальцами его локоть и таким тоном, как будто то, что он говорил, было давным давно решено между ними и не могло быть решено иначе.
– Завтра мы едем, я тебе даю место в своей коляске. Я очень рад. Здесь у нас всё важное покончено. А мне уж давно бы надо. Вот я получил от канцлера. Я его просил о тебе, и ты зачислен в дипломатический корпус и сделан камер юнкером. Теперь дипломатическая дорога тебе открыта.
Несмотря на всю силу тона усталости и уверенности, с которой произнесены были эти слова, Пьер, так долго думавший о своей карьере, хотел было возражать. Но князь Василий перебил его тем воркующим, басистым тоном, который исключал возможность перебить его речь и который употреблялся им в случае необходимости крайнего убеждения.
– Mais, mon cher, [Но, мой милый,] я это сделал для себя, для своей совести, и меня благодарить нечего. Никогда никто не жаловался, что его слишком любили; а потом, ты свободен, хоть завтра брось. Вот ты всё сам в Петербурге увидишь. И тебе давно пора удалиться от этих ужасных воспоминаний. – Князь Василий вздохнул. – Так так, моя душа. А мой камердинер пускай в твоей коляске едет. Ах да, я было и забыл, – прибавил еще князь Василий, – ты знаешь, mon cher, что у нас были счеты с покойным, так с рязанского я получил и оставлю: тебе не нужно. Мы с тобою сочтемся.
То, что князь Василий называл с «рязанского», было несколько тысяч оброка, которые князь Василий оставил у себя.
В Петербурге, так же как и в Москве, атмосфера нежных, любящих людей окружила Пьера. Он не мог отказаться от места или, скорее, звания (потому что он ничего не делал), которое доставил ему князь Василий, а знакомств, зовов и общественных занятий было столько, что Пьер еще больше, чем в Москве, испытывал чувство отуманенности, торопливости и всё наступающего, но не совершающегося какого то блага.
Из прежнего его холостого общества многих не было в Петербурге. Гвардия ушла в поход. Долохов был разжалован, Анатоль находился в армии, в провинции, князь Андрей был за границей, и потому Пьеру не удавалось ни проводить ночей, как он прежде любил проводить их, ни отводить изредка душу в дружеской беседе с старшим уважаемым другом. Всё время его проходило на обедах, балах и преимущественно у князя Василия – в обществе толстой княгини, его жены, и красавицы Элен.
Анна Павловна Шерер, так же как и другие, выказала Пьеру перемену, происшедшую в общественном взгляде на него.
Прежде Пьер в присутствии Анны Павловны постоянно чувствовал, что то, что он говорит, неприлично, бестактно, не то, что нужно; что речи его, кажущиеся ему умными, пока он готовит их в своем воображении, делаются глупыми, как скоро он громко выговорит, и что, напротив, самые тупые речи Ипполита выходят умными и милыми. Теперь всё, что ни говорил он, всё выходило charmant [очаровательно]. Ежели даже Анна Павловна не говорила этого, то он видел, что ей хотелось это сказать, и она только, в уважение его скромности, воздерживалась от этого.
В начале зимы с 1805 на 1806 год Пьер получил от Анны Павловны обычную розовую записку с приглашением, в котором было прибавлено: «Vous trouverez chez moi la belle Helene, qu'on ne se lasse jamais de voir». [у меня будет прекрасная Элен, на которую никогда не устанешь любоваться.]
Читая это место, Пьер в первый раз почувствовал, что между ним и Элен образовалась какая то связь, признаваемая другими людьми, и эта мысль в одно и то же время и испугала его, как будто на него накладывалось обязательство, которое он не мог сдержать, и вместе понравилась ему, как забавное предположение.
Вечер Анны Павловны был такой же, как и первый, только новинкой, которою угощала Анна Павловна своих гостей, был теперь не Мортемар, а дипломат, приехавший из Берлина и привезший самые свежие подробности о пребывании государя Александра в Потсдаме и о том, как два высочайшие друга поклялись там в неразрывном союзе отстаивать правое дело против врага человеческого рода. Пьер был принят Анной Павловной с оттенком грусти, относившейся, очевидно, к свежей потере, постигшей молодого человека, к смерти графа Безухого (все постоянно считали долгом уверять Пьера, что он очень огорчен кончиною отца, которого он почти не знал), – и грусти точно такой же, как и та высочайшая грусть, которая выражалась при упоминаниях об августейшей императрице Марии Феодоровне. Пьер почувствовал себя польщенным этим. Анна Павловна с своим обычным искусством устроила кружки своей гостиной. Большой кружок, где были князь Василий и генералы, пользовался дипломатом. Другой кружок был у чайного столика. Пьер хотел присоединиться к первому, но Анна Павловна, находившаяся в раздраженном состоянии полководца на поле битвы, когда приходят тысячи новых блестящих мыслей, которые едва успеваешь приводить в исполнение, Анна Павловна, увидев Пьера, тронула его пальцем за рукав.
– Attendez, j'ai des vues sur vous pour ce soir. [У меня есть на вас виды в этот вечер.] Она взглянула на Элен и улыбнулась ей. – Ma bonne Helene, il faut, que vous soyez charitable pour ma рauvre tante, qui a une adoration pour vous. Allez lui tenir compagnie pour 10 minutes. [Моя милая Элен, надо, чтобы вы были сострадательны к моей бедной тетке, которая питает к вам обожание. Побудьте с ней минут 10.] А чтоб вам не очень скучно было, вот вам милый граф, который не откажется за вами следовать.
Красавица направилась к тетушке, но Пьера Анна Павловна еще удержала подле себя, показывая вид, как будто ей надо сделать еще последнее необходимое распоряжение.
– Не правда ли, она восхитительна? – сказала она Пьеру, указывая на отплывающую величавую красавицу. – Et quelle tenue! [И как держит себя!] Для такой молодой девушки и такой такт, такое мастерское уменье держать себя! Это происходит от сердца! Счастлив будет тот, чьей она будет! С нею самый несветский муж будет невольно занимать самое блестящее место в свете. Не правда ли? Я только хотела знать ваше мнение, – и Анна Павловна отпустила Пьера.
Пьер с искренностью отвечал Анне Павловне утвердительно на вопрос ее об искусстве Элен держать себя. Ежели он когда нибудь думал об Элен, то думал именно о ее красоте и о том не обыкновенном ее спокойном уменьи быть молчаливо достойною в свете.
