Перейти до вмісту

Структури даних


Повідомлень в темі: 2

#1 Amarok

    Старійшина

  • Користувачі
  • PipPipPipPipPipPipPipPipPipPip
  • 2350 повідомлень
  • Стать:Чоловік
  • Місто:Дубно -> Нетішин -> Київ -> New York

Відправлено 13.03.2011 – 00:03

  • 2
Сюди скидати питання та обговорення теорії структур даних та алгоритмів повязаних з ними...

Отже, я перший.
Викладачка, підручник та ґуґл кажуть що мінімальна кількість елементів у купі (heap) http://latex.codecog.../gif.latex?2^h.
Але виходить що для висоти 1 кількість елементів 2. А 2 елементи це навіть не дерево, (список взагалі-то)
За визначенням купа - це майже повне бінарне дерево. Тобто щоб задовольнити це визначення мінімальна кількість має бути http://latex.codecog.../gif.latex?2^h?

П.С. цікаво що як це що таких тем по теоретичній інформатиці тут не було...

Повідомлення відредагував Amarok: 13.03.2011 – 00:06


#2 eaebeeed49413332

    Частий гість

  • Заблоковані
  • PipPipPip
  • 65 повідомлень

Відправлено 13.03.2011 – 01:05

Перегляд дописуAmarok (13.03.2011 00:03) писав:

Сюди скидати питання та обговорення теорії структур даних та алгоритмів повязаних з ними...

Отже, я перший.
Викладачка, підручник та ґуґл кажуть що мінімальна кількість елементів у купі (heap) http://latex.codecog.../gif.latex?2^h.
Але виходить що для висоти 1 кількість елементів 2. А 2 елементи це навіть не дерево, (список взагалі-то)
За визначенням купа - це майже повне бінарне дерево. Тобто щоб задовольнити це визначення мінімальна кількість має бути http://latex.codecog.../gif.latex?2^h?

П.С. цікаво що як це що таких тем по теоретичній інформатиці тут не було...
бінарна купа. формула має задовільняти всім допустимим h. h=1 - часний випадок, де купа з мінімальною кількістю елементів схожа на список.
  • 0

#3 Amarok

    Старійшина

  • Користувачі
  • PipPipPipPipPipPipPipPipPipPip
  • 2350 повідомлень
  • Стать:Чоловік
  • Місто:Дубно -> Нетішин -> Київ -> New York

Відправлено 13.03.2011 – 01:57

Перегляд дописуeaebeeed49413332 (12.03.2011 18:05) писав:

бінарна купа. формула має задовільняти всім допустимим h. h=1 - часний випадок, де купа з мінімальною кількістю елементів схожа на список.

тобто для мінімуму купа не є купою?
бо так для висоти 2 мінімум 4 що є тру (див рисунок купи)
  • 0



Кількість користувачів, що читають цю тему: 1

0 користувачів, 1 гостей, 0 анонімних