Kahendkuhi (binary heap) ja sorteerimine kuhjameetodil (heap sort).
Kuhjaomadus: puu ühegi tipu võti pole suurem kui tema ülemuse võti (mittekasvavad jadad juurest alla).
Kahendkuhi (edaspidi lihtsalt kuhi) on kuhjaomadusega kompaktne kahendpuu. Suurim võti on puu juurtipus.
Overview
One simple way to sort a list of objects is to use a heap data structure. All elements to be sorted are inserted into a heap, and the heap organizes the elements added to it in such a way that either the largest value (in a max-heap) or the smallest value (in a min-heap) can be quickly extracted. Moreover, because this operation preserves the heap's structure, the largest/smallest value can be repeatedly extracted until none remain. This gives us the elements in order.
In doing so, the only extra space required is that needed to store the heap. In order to achieve constant space overhead, we use a trick: we store a binary heap (or alternatively, a heap with more than two children) inside the part of the input array which has not yet been sorted. (The structure of this heap is described at Binary heap: Heap implementation.) Heapsort makes use of two standard heap operations: insertion and root deletion. Each time we delete (extract) the maximum, we place it in the last location of the array not yet occupied, and use the remaining prefix of the array as a heap holding the remaining unsorted elements: