Content deleted Content added
m Removed invisible unicode characters + other fixes, replaced: → (33) using AWB (11754) |
m Added in wiki link to binary tree |
||
Line 41:
=== Binary Tree Implementation ===
As an example, the above technique can be implemented using a [[binary tree]] for its priority queue.<ref>{{Cite book|title = Fundamentals of data structures|url = https://books.google.com/books?id=kdRQAAAAMAAJ|publisher = Computer Science Press|date = 1983-01-01|isbn = 9780914894209|first = Ellis|last = Horowitz|first2 = Sartaj|last2 = Sahni}}</ref> This can help limit the number of comparisons between the element heads. The binary tree is built containing the results of comparing the head of each array. The topmost node of the binary tree is then popped off and its leaf is refilled with the next element in its array.
As an example, let's say we have 4 sorted arrays:<ref>{{Cite web|title = kway - Very fast merge sort - Google Project Hosting|url = https://code.google.com/p/kway/|website = code.google.com|accessdate = 2015-11-22}}</ref><blockquote><code>{5, 10, 15, 20}</code></blockquote><blockquote><code>{10, 13, 16, 19}</code></blockquote><blockquote><code>{2, 19, 26, 40}</code> </blockquote><blockquote><code>{18, 22, 23, 24}</code></blockquote>We start with the heads of each array and then build a binary tree from there.
| |||