Heap sort
Heap sort is an improvised form of selection sort, wherein the algorithm initially splits the input vector into sorted and unsorted vectors, and then iteratively shrinks the unsorted vector by extracting the largest element and placing it in the sorted vector. It is based on the heap data structure which provides a non-quadratic asymptote even for the worst-case scenarios. Heaps are tree-based data structures with the following properties:
- Shape criterion: Heaps are primarily complete binary trees with both the left and right child nodes filled with values:
Figure 5.10: Illustration of complete and in-complete binary tree
- Heap criterion ...
Get R Data Structures and Algorithms now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
