Реализация структуры данных двоичной кучи с использованием C#, который может принимать Generi c типы и вставлять / сортировать через свойство значения - PullRequest
0 голосов
/ 11 июля 2020

Я пытаюсь объединить K отсортированных связанных списков, используя двоичную структуру кучи MinHeap. В настоящее время у меня есть правильная реализация Min / MaxHeap в C#, которую я использовал для задач кодирования, но она принимает только целые числа.

Какую реализацию я могу использовать для C#, если я хочу использовать MinHeap, который накапливается на основе свойства ListNode int Value?

Я везде искал работающую реализацию PriorityQueue или Binary Heap C# для использования во время собеседований по кодированию, но мне еще предстоит найти ту, которая правильно принимает Generi c Типы и может быть отсортирован через свойство (возможно, с IComparable?)

Для реализации Java того, что я описываю, я привел пример ниже:

import java.util.*;

class ListNode {
  int value;
  ListNode next;

  ListNode(int value) {
    this.value = value;
  }
}

class MergeKSortedLists {

  public static ListNode merge(ListNode[] lists) {
    PriorityQueue<ListNode> minHeap = new PriorityQueue<ListNode>((n1, n2) -> n1.value - n2.value);

    // put the root of each list in the min heap
    for (ListNode root : lists)
      if (root != null)
        minHeap.add(root);

    // take the smallest (top) element form the min-heap and add it to the result; 
    // if the top element has a next element add it to the heap
    ListNode resultHead = null, resultTail = null;
    while (!minHeap.isEmpty()) {
      ListNode node = minHeap.poll();
      if (resultHead == null) {
        resultHead = resultTail = node;
      } else {
        resultTail.next = node;
        resultTail = resultTail.next;
      }
      if (node.next != null)
        minHeap.add(node.next);
    }

    return resultHead;
  }

  public static void main(String[] args) {
    ListNode l1 = new ListNode(2);
    l1.next = new ListNode(6);
    l1.next.next = new ListNode(8);

    ListNode l2 = new ListNode(3);
    l2.next = new ListNode(6);
    l2.next.next = new ListNode(7);

    ListNode l3 = new ListNode(1);
    l3.next = new ListNode(3);
    l3.next.next = new ListNode(4);

    ListNode result = MergeKSortedLists.merge(new ListNode[] { l1, l2, l3 });
    System.out.print("Here are the elements form the merged list: ");
    while (result != null) {
      System.out.print(result.value + " ");
      result = result.next;
    }
  }
}

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...