我不認(rèn)為你的代碼產(chǎn)生的結(jié)果應(yīng)該優(yōu)先于queuedAt它應(yīng)該產(chǎn)生的結(jié)果。您的算法首先對(duì)以queuedAt錯(cuò)誤位置順序出現(xiàn)的元素進(jìn)行排序，然后交換出現(xiàn)位置順序的元素，但這并不總是導(dǎo)致盡可能優(yōu)先的順序queuedAt。
例如，在您的輸出中，元素 withqueuedAt=3出現(xiàn)在元素 with之后queuedAt=2，但它們沒(méi)有理由不能以相反的順序出現(xiàn)：當(dāng)它們屬于同一隊(duì)列時(shí)，調(diào)整后的排序仍會(huì)按其位置順序列出項(xiàng)目，但會(huì)優(yōu)先考慮更大的queuedAt值。
建議的算法
為了糾正這個(gè)缺點(diǎn)并獲得更好的時(shí)間復(fù)雜度，您可以使用最大堆。該堆中的一個(gè)條目將對(duì)應(yīng)于一個(gè)隊(duì)列，其所有元素均按 排序position。堆使用的鍵是隊(duì)列第一個(gè)元素的屬性，即具有最小值的元素。queuedAtposition
然后，您將從堆中選擇頂部條目（隊(duì)列），從該隊(duì)列中提取第一個(gè)元素，并將其推送到最終結(jié)果。如果隊(duì)列尚未為空，則將其保留在堆上，但調(diào)整其key，因此它再次對(duì)應(yīng)于queuedAt現(xiàn)在第一個(gè)（least?position）的隊(duì)列元素的屬性。如果隊(duì)列已耗盡，則將其從堆中刪除。如果您繼續(xù)這樣做直到堆被清空，您將按照所需的順序訪問(wèn)條目。
不幸的是，JavaScript 沒(méi)有本機(jī)堆實(shí)現(xiàn)。所以你必須扔掉你自己的，或者包括一個(gè)庫(kù)（有幾個(gè)）。
在下面的實(shí)現(xiàn)中，我選擇以相反的順序?qū)﹃?duì)列進(jìn)行排序，因此我可以按所需的順序彈出元素。
開(kāi)始了：
/* MinHeap minimised - taken from https://stackoverflow.com/a/66511107/5459839 */
const MaxHeap={siftDown(h,i=0,v=h[i]){if(i<h.length){let k=v[0];while(1){let j=i*2+1;if(j+1<h.length&&h[j][0]<h[j+1][0])j++;if(j>=h.length||k>=h[j][0])break;h[i]=h[j];i=j;}h[i]=v}},heapify(h){for(let i=h.length>>1;i--;)this.siftDown(h,i);return h},pop(h){return this.exchange(h,h.pop())},exchange(h,v){if(!h.length)return v;let w=h[0];this.siftDown(h,0,v);return w},push(h,v){let k=v[0],i=h.length,j;while((j=(i-1)>>1)>=0&&k>h[j][0]){h[i]=h[j];i=j}h[i]=v;return h}};
// Main function
function customSort(data) {
? // Create a map with a key for each queue
? let map = new Map(data.map(o => [o.queueName, []]));
? // Populate the map entries
? for (let o of data) map.get(o.queueName).push(o);
? // We have no more need of the Map:
? let queues = [...map.values()];
? // Sort each queue by descending position (so we can pop from those queues in ascending order)
? for (let queue of queues) queue.sort((a, b) => b.position - a.position);
? // Build a heap of pairs, where first value in pair is the heap key, and the second is the payload (the queue)
? let heap = MaxHeap.heapify(queues.map(queue => [queue[queue.length - 1].enqueuedAt, queue]));
? let result = [];
? while (heap.length) {
? ? // Peek in the heap, to get the "top" queue
? ? let queue = heap[0][1];
? ? // Extract the element from that queue with the lowest position
? ? result.push(queue.pop());
? ? if (queue.length) {
? ? ? // Adapt the key of this queue on the heap
? ? ? MaxHeap.exchange(heap, [queue[queue.length - 1].enqueuedAt, queue]);
? ? } else {
? ? ? // Remove the now empty queue from the heap
? ? ? MaxHeap.pop(heap);
? ? }
? }
? return result;
}
// Example data from the question:
const data = [{id: 1,enqueuedAt: 8,queueName: 'Queue 1',position: 1},{id: 2,enqueuedAt: 7,queueName: 'Queue 2',position: 1},{id: 3,enqueuedAt: 6,queueName: 'Queue 3',position: 3},{id: 4,enqueuedAt: 5,queueName: 'Queue 4',position: 2},{id: 5,enqueuedAt: 1,queueName: 'Queue 1',position: 2},{id: 6,enqueuedAt: 2,queueName: 'Queue 4',position: 1},{id: 7,enqueuedAt: 4,queueName: 'Queue 1',position: 3},{id: 8,enqueuedAt: 3,queueName: 'Queue 2',position: 2}]
console.log(customSort(data));
時(shí)間復(fù)雜度為O(nlogn)，就像普通的基于比較的排序一樣
沒(méi)有堆的解決方案
可以在不使用堆的情況下在 JavaScript 中實(shí)現(xiàn)此操作，但它需要requiredAt范圍有限（但它仍然是一個(gè)很大的范圍： 2?32）：我們可以利用 JavaScript 在普通情況下保證的關(guān)鍵迭代順序自2017-2020 年語(yǔ)言規(guī)范更新以來(lái)的對(duì)象。
堆中的requiredAt鍵在哪里，它可以成為普通對(duì)象中的鍵。由于您需要降序排列，我們必須應(yīng)用requiredAt到可以按升序迭代的正整數(shù)的映射。映射可以類(lèi)似于：32000 - requiredAt。
下面是如何編碼：
function customSort(data) {
? // Create a map with a key for each queue
? let map = new Map(data.map(o => [o.queueName, []]));
? // Populate the map entries
? for (let o of data) map.get(o.queueName).push(o);
? // We have no more need of the Map:
? let queues = [...map.values()];
? // Sort each queue by descending position (so we can pop from those queues in ascending order)
? for (let queue of queues) queue.sort((a, b) => b.position - a.position);
? // Build an object keyed by "negative" `queuedAt`
? const MAX = 2 ** 31 - 1;
? let sorted = Object.fromEntries(queues.map(queue => [MAX - queue[queue.length - 1].enqueuedAt, queue]));
? let result = [];
? for (let i = 0; i < data.length; i++) {
? ? // Use JS behaviour where index keys are iterated in numerical order
? ? let queuedAt;
? ? for (queuedAt in sorted) break;
? ? // Get the queue at this (first) key and remove the entry
? ? let queue = sorted[queuedAt];
? ? delete sorted[queuedAt];
? ? // Extract the element from that queue with the lowest position
? ? result.push(queue.pop());
? ? if (queue.length) {
? ? ? // Store the shortened queue at its new key
? ? ? sorted[MAX - queue[queue.length - 1].enqueuedAt] = queue;
? ? }
? }
? return result;
}
// Example data from the question:
const data = [{id: 1,enqueuedAt: 8,queueName: 'Queue 1',position: 1},{id: 2,enqueuedAt: 7,queueName: 'Queue 2',position: 1},{id: 3,enqueuedAt: 6,queueName: 'Queue 3',position: 3},{id: 4,enqueuedAt: 5,queueName: 'Queue 4',position: 2},{id: 5,enqueuedAt: 1,queueName: 'Queue 1',position: 2},{id: 6,enqueuedAt: 2,queueName: 'Queue 4',position: 1},{id: 7,enqueuedAt: 4,queueName: 'Queue 1',position: 3},{id: 8,enqueuedAt: 3,queueName: 'Queue 2',position: 2}]
console.log(customSort(data));
最后的評(píng)論
請(qǐng)注意順序與您的輸出有何不同，但仍然符合您設(shè)定的規(guī)則。該解決方案中的順序確實(shí)最大化了 的優(yōu)先級(jí)enqueuedAt。
