將k個有序鏈表合并成一個有序鏈表

這里以從小到大排序為例，
時間復雜度為O（nlgk）。
特點：利用最小堆來完成k路歸并
思路：取每個列表中的第一個元素，并將其放在最小堆中。與每個元素一起，必須跟蹤從哪個列表中獲取它。當合并時，從堆中取最小的元素，然后從它的來源列表中插入另一個元素(除非列表為空，為空時最小堆減少)。繼續執行，直到清空堆。

輔助類：1?? KeyValuePair
跟蹤是哪個鏈表

class KeyValuePair { public:int key;int value; public:KeyValuePair();KeyValuePair(int key,int value); }; KeyValuePair::KeyValuePair(){} KeyValuePair::KeyValuePair(int key,int value):key(key),value(value){};

2??MinimumHeapTemplate
模版類最小堆的構建
里面所含的頭文件代碼：堆排序

#include "heap_sort.h" #include <iostream> using namespace std; template <typename T> void min_heapify(vector<T>& array,int heap_size,int parent_index) {int smallest = parent_index;int l = left(parent_index);int r = right(parent_index);if(l<heap_size && array[l].key<array[smallest].key)smallest = l;if(r<heap_size && array[r].key<array[smallest].key)smallest = r;if(parent_index != smallest){T temp = array[smallest];array[smallest] = array[parent_index];array[parent_index] = temp;min_heapify(array,heap_size,smallest);} }template <typename T> void build_min_heap(vector<T>& array,int length) {for(int i= length/2;i>=0;i--){min_heapify(array,length,i);} }

最終合并實現

#include "MinimumHeapTemplate.h" #include "KeyValuePair.h" #include <vector> #include <stdexcept>using namespace std; void merge_ordered_arrays(int **array,int row,int column,int *out_array);void merge_ordered_arrays(int **array,int row,int column,int *out_array){vector<KeyValuePair> heap_sort_array(row);int *count_array = new int [row];int heap_size = row;for (int i = 0; i < row; ++i) {count_array[i] = 1;}for (int i = 0; i < row; ++i) {heap_sort_array[i].key = array[i][0];heap_sort_array[i].value = i;}build_min_heap(heap_sort_array,row);int index = 0;while (heap_size>0){KeyValuePair top = heap_sort_array[0];out_array[index] = top.key;index++;if(count_array[top.value]<column){heap_sort_array[0].key = array[top.value][count_array[top.value]];heap_sort_array[0].value = top.value;count_array[top.value]++;min_heapify(heap_sort_array,heap_size,0);}else{heap_size--;heap_sort_array[0] = heap_sort_array[heap_size];min_heapify(heap_sort_array,heap_size,0);}}delete [] count_array; }

總結

以上是生活随笔為你收集整理的将k个有序链表合并成一个有序链表的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。