найбільш рекомендованих

Ну так, ще раз про іспити, знову про навчання, і я приходжу до розділу, в якому сказане книгою мене дивує, і, впроваджуючи це, я підтверджую себе. Теорія або те, що є в книгах, не є 100% надійною, у випадку математичних, фізичних теорій, ... чи обчислень, ми повинні перевірити, що нам говорять книги, тому що ми можемо знайти помилку.

Оновлення: якщо ви хочете побачити, як зробити код кургану за допомогою Еліксиру, ви можете побачити цей запис.

Беручи до уваги, що те, що книга вказує, є псевдокодом, це ще гірше, оскільки той, хто пише, впевнений, що це добре робить, і я не сумніваюся, що він навіть перевірив це, але, звичайно, ми знаходимо це, оскільки він не є мовною конкретністю, це може бути інтерпретація реалізації, для якої, можливо, було втрачено якусь суть на шляху, або допустити друкарську помилку.

Але до суті. Кургани.

Ця структура даних була запропонована Робертом В. Флойдом (премія Тьюрінга в 1978 р.) Для вирішення проблеми впорядкування елементів у векторі, знаменитої купи (або замовлення за купою).

У предметі Програмування та вдосконалені структури даних (на бакалавраті комп'ютерної інженерії в UNED) пропонується на початку предмета, як знання структур даних, курган.

Курган, хоча і концептуально намальований у формі дерева, реалізований на векторі. Оскільки він збалансований і двійковий, вузол може містити лише двох дітей. Формула доступу до кожної дитини, враховуючи батьківський індекс (i), мала б вигляд:

Доступ до батьківського елемента здійснювався б за допомогою цілочисельного ділення: i/2 .

Сам курган дозволяє:

  • Упорядковуйте елементи вектора простим та оптимальним способом, маючи можливість реалізувати власний порівняльник.
  • Шукає максимуми, мінімуми або будь-який інший фактор, який враховується при виборі елементів пошуку.
  • У специфічних для графіків задачах, таких як мінімальне покриття Прима або найкоротший шлях Дейкстри.

Реалізація алгоритму

Мені знадобилося трохи, щоб визначити мову, якою його реалізувати, нарешті, я вибрав Ruby, оскільки його код цілком псевдокодований, але це було б так само добре в Python. Код буде таким:

Після того, як ми побачили весь код, ми можемо виконати тест, подібний до наведеного нижче, в який ми вставимо деякі випадкові дані і отримаємо результат їх зберігання у вигляді купи, а результат у впорядкованому векторі:

Результат такий:

ПРИМІТКА: Як видно з реалізації, цей код був підготовлений для векторів, які перераховували свої елементи на основі 1.N, і все ж усі мови (за винятком Pascal, Modula - 2 тощо) нумерують вектори від 0.N - 1, тому в кожному доступі до атрибута @vector число потрібно було зменшити на 1, щоб перейти від позначення 1.N до 0.N - 1.

Висновки