Swipe to navigate through the chapters of this book
Please log in to get access to this content
To get access to this content you need the following product:
Note that some authors use the conquer term for the base case of the recursion, yielding the slightly different ordering: divide, conquer, and combine.
Described by Udi Manber in his Introduction to Algorithms (see “References” in Chapter 4).
For example, in the skyline problem, you would probably want to split the base case element ( L, H, R) into two pairs, ( L, H) and ( R, H), so the combine function can build a sequence of points.
Actually, more flexible may not be entirely correct. There are many objects (such as complex numbers) that can be hashed but that cannot be compared for size.
In statistics, the median is also defined for sequences of even length. It is then the average of the two middle elements. That’s not an issue we worry about here.
In theory, we could use the guaranteed linear version of select to find the median and use that as a pivot. That’s not something likely to happen in practice, though.
Timsort is, in fact, also used in Java SE 7, for sorting arrays.
See, for example, the file listsort.txt in the source code (or online, http://svn.python.org/projects/python/ trunk/Objects/listsort.txt).
You can find the actual C code at http://svn.python.org/projects/python/trunk/Objects/listobject.c .
Real numbers usually aren’t all that arbitrary, of course. As long as your numbers use a fixed number of bits, you can use radix sort (mentioned in Chapter 4) and sort the values in linear time.
I think that’s so cool, I wanted to add an exclamation mark after the sentence ... but I guess that might have been a bit confusing, given the subject matter.
Actually, the approximation isn’t asymptotic in nature. If you want the details, you’ll find them in any good mathematics reference.
A region is convex if you can draw a line between any two points inside it, and the line stays inside the region.
I’m still assuming that we want a nonempty interval. If it turns out to have a negative sum, you could always use an empty interval instead.
This section is a bit hard and is not essential in order to understand the rest of the book. Feel free to skim it or even skip it entirely. You might want to read the “Black Box” sidebar on binary heaps, heapq, and heapsort, though, later in the section.
The AA-tree is, in a way, a version of the BB-tree, or the binary B-tree, which was introduced by Rudolph Bayer in 1971 as a binary representation of the 2-3-tree.
It is quite common to call this operation build-heap and to reserve the name heapify for the operation that repairs a single node. Thus, build-heap runs heapify on all nodes but the leaves.
- Divide, Combine, and Conquer
Magnus Lie Hetland
- Sequence number
- Chapter number
- Chapter 6