Heapsort
- Date
- 1964 · confidence high
- Place
- Borehamwood, England, United Kingdom
- Credited to
- J. W. J. Williams
- Field
- Knowledge & symbols
What it is
Williams published the heapsort algorithm, which first reorganizes an array into a binary heap — a structure where each node is larger than its children — and then repeatedly extracts the maximum to produce a sorted list in place in n log n time. That same year, Robert W. Floyd improved the heap-building method.
What it led to
- Efficient in-place sorting algorithms
- Heap-based priority queues
Built on
- Binary tree
Made possible
- Priority queue (heap)