Heap Type in C, C++, Java, Python and C#: Code and Prices

Heap kind has the assure quicksort lacks and the reminiscence use merge kind lacks: O(n log n) on each enter, sorted in place. On 10,000 values its comparability depend stayed between 217,379 and 244,460 throughout 4 very totally different inputs. It pays for that in velocity. On random integers it took as much as 1.5 instances so long as a quicksort as much as 1,000,000 parts, and 1.7–2.1 instances as lengthy at ten million, underneath two compilers.

This information reveals how a heap is saved in an array and traces heap kind on a small instance. It offers implementations in C, C++, Java, Python and C#, and measures the 2 methods to construct a heap, Floyd’s variant that saves 41% of the comparisons, and the timing hole with quicksort. It closes with three index errors, one in every of which sorted the article’s personal instance accurately and failed on 8.7% of random inputs. Each program was compiled and run for this text on Ubuntu 24.04: C with GCC 13.3 and Clang 18.1.3 (-std=c11 and -std=c17), C++ with g++ 13.3 and clang++ 18.1.3 (-std=c++17 and -std=c++20), all with -Wall -Wextra -pedantic and no warnings besides the place a pitfall is proven; Java on OpenJDK 21, Python 3.11 (additionally checked with ruff and mypy --strict), and C# on .NET 10 with analyzer warnings as errors. All 5 kind the identical array and print the identical outcome. The C and C++ code is in GitHub repositories whose builds run the exams on every change.

What Is Heap Type?

Heap kind is a comparability sorting algorithm that arranges the array right into a binary max-heap, through which each ingredient is a minimum of as giant as its kids, after which repeatedly swaps the most important ingredient (on the root) to the top of the array and restores the heap within the half that continues to be. It kinds in place with O(1) further reminiscence, runs in O(n log n) time within the worst case, and isn’t steady.

It’s choice kind with a greater information construction. Each repeatedly take the most important (or smallest) remaining ingredient; choice kind finds it with an O(n) scan, heap kind retains the remaining parts in a heap so that every elimination prices O(log n). The algorithm was printed by J. W. J. Williams in 1964, and the O(n) bottom-up approach of constructing the heap by Robert W. Floyd the identical 12 months; NIST’s Dictionary of Algorithms and Information Buildings lists each papers. Heap kind’s worst-case assure is why it seems inside different kinds: libstdc++’s std::kind and OpenJDK’s Arrays.kind for primitive arrays each swap to heap kind when quicksort’s recursion goes too deep.

How a Heap Lives in an Array

A binary heap wants no pointers. For an array listed from 0, the youngsters of index i are at 2i + 1 and 2i + 2, and its mum or dad is at (i − 1) / 2. The heap property says each ingredient is a minimum of as giant as its kids, which places the most important worth at index 0.

Two operations keep the property:

• Sift down: a component which may be too small for its place is swapped with its bigger youngster till neither youngster is bigger. That is how the foundation is restored after the most important ingredient is eliminated.
• Sift up: a component which may be too giant is swapped with its mum or dad till the mum or dad isn’t smaller. That is how a component is inserted.

How Heap Type Works

1. Construct a max-heap from the entire array. The environment friendly approach is to sift down each inner node, ranging from the final mum or dad at index n/2 − 1 and dealing again to the foundation.
2. Swap a[0], the most important ingredient, with the final ingredient of the heap. The most important is now in its remaining place.
3. Shrink the heap by one and sift down the brand new root.
4. Repeat steps 2 and three till the heap has one ingredient.

Labored Instance

Sorting 29 10 14 37 13 5 41 22, as printed by the hint program within the repository. The | separates the heap on the left from the sorted tail on the suitable:

Output:

begin:                   29   10   14   37   13    5   41   22
max-heap constructed:          41   37   29   22   13    5   14   10
extract 41:              37   22   29   10   13    5   14 | 41
extract 37:              29   22   14   10   13    5 | 37   41
extract 29:              22   13   14   10    5 | 29   37   41
extract 22:              14   13    5   10 | 22   29   37   41
extract 14:              13   10    5 | 14   22   29   37   41
extract 13:              10    5 | 13   14   22   29   37   41
extract 10:               5 | 10   13   14   22   29   37   41

Constructing the heap moved 41 from index 6 to the foundation and 29 all the way down to index 2, the place it sits above 5 and 14. After that, every line takes the foundation, swaps it behind the |, and sifts the brand new root down. After “extract 41” the foundation is 37, the bigger of the 2 kids that 41 left behind, as a result of 10, swapped up from the top, sank previous it.

Heap Type in C

The header declares the type, Floyd’s variant, and each heap-building strategies, that are measured individually beneath:

/* heap_sort.h - heap kind for int arrays, and the 2 methods to construct a heap */
#ifndef HEAP_SORT_H
#outline HEAP_SORT_H

#embody <stddef.h>

void heap_sort(int a[], size_t n);         /* sift-down, bottom-up construct  */
void heap_sort_floyd(int a[], size_t n);   /* Floyd's leaf-first variant  */

void make_heap_down(int a[], size_t n);    /* bottom-up construct: O(n)       */
void make_heap_up(int a[], size_t n);      /* insert one by one: O(n log n) */

#endif

/* heap_sort.c - heap kind in C11, with a max-heap saved within the array:
 * the youngsters of index i are at 2i + 1 and 2i + 2, its mum or dad at (i - 1) / 2.
 * SORT_LESS(x, y) means "x kinds earlier than y". Check applications redefine it
 * earlier than together with this file, to depend comparisons. */
#embody "heap_sort.h"

#ifndef SORT_LESS
#outline SORT_LESS(x, y) ((x) < (y))
#endif

static void swap_int(int *x, int *y) { int t = *x; *x = *y; *y = t; }

/* Strikes a[root] down till neither youngster is bigger. The heap is a[0..n). */
static void sift_down(int a[], size_t root, size_t n)
{
    for (;;) {
        size_t youngster = 2 * root + 1;
        if (youngster >= n)
            return;                          /* root is a leaf */
        if (youngster + 1 < n && SORT_LESS(a[child], a[child + 1]))
            youngster++;                         /* the bigger youngster */
        if (!SORT_LESS(a[root], a[child]))
            return;                          /* heap order holds */
        swap_int(&a[root], &a[child]);
        root = youngster;
    }
}

/* Strikes a[i] up till its mum or dad isn't smaller. */
static void sift_up(int a[], size_t i)
{
    whereas (i > 0) {
        size_t mum or dad = (i - 1) / 2;
        if (!SORT_LESS(a[parent], a[i]))
            return;
        swap_int(&a[parent], &a[i]);
        i = mum or dad;
    }
}

/* Floyd's bottom-up heapify: repair the subtrees from the final mum or dad again. */
void make_heap_down(int a[], size_t n)
{
    for (size_t i = n / 2; i-- > 0; )        /* n / 2 - 1 all the way down to 0, no wrap */
        sift_down(a, i, n);
}

/* Builds the heap by inserting a[1], a[2], ... one by one. */
void make_heap_up(int a[], size_t n)
{
    for (size_t i = 1; i < n; i++)
        sift_up(a, i);
}

/* In place, O(n log n) worst case, not steady. */
void heap_sort(int a[], size_t n)
{
    make_heap_down(a, n);
    for (size_t finish = n; finish > 1; end--) {
        swap_int(&a[0], &a[end - 1]);        /* largest to its remaining place */
        sift_down(a, 0, finish - 1);
    }
}

/* Floyd's variant: the ingredient moved to the foundation is nearly all the time small,
 * so stroll the larger-child path all the best way to a leaf with out evaluating
 * in opposition to it (one comparability per stage as an alternative of two), then climb again
 * as much as the place it belongs. */
void heap_sort_floyd(int a[], size_t n)
{
    make_heap_down(a, n);
    for (size_t finish = n; finish > 1; end--) {
        size_t m = finish - 1;                  /* heap is a[0..m) after the swap */
        int v = a[m];
        a[m] = a[0];                         /* largest to its remaining place */
        size_t gap = 0;
        for (;;) {                           /* 1. descend to a leaf */
            size_t youngster = 2 * gap + 1;
            if (youngster >= m)
                break;
            if (youngster + 1 < m && SORT_LESS(a[child], a[child + 1]))
                youngster++;
            a[hole] = a[child];
            gap = youngster;
        }
        whereas (gap > 0) {                   /* 2. climb again as much as v's place */
            size_t mum or dad = (gap - 1) / 2;
            if (!SORT_LESS(a[parent], v))
                break;
            a[hole] = a[parent];
            gap = mum or dad;
        }
        a[hole] = v;
    }
}

A brief program that calls them:

/* heap_example.c - builds a heap, then kinds, with each variants */
#embody <stdio.h>
#embody <limits.h>
#embody "heap_sort.h"

static void print_array(const char *label, const int a[], size_t n)
{
    printf("%-10s", label);
    for (size_t i = 0; i < n; i++)
        printf(" %d", a[i]);
    printf("n");
}

int most important(void)
{
    int a[] = { 29, 10, 14, 37, 13, 5, 41, 22 };
    int b[] = { 29, 10, 14, 37, 13, 5, 41, 22 };
    int h[] = { 29, 10, 14, 37, 13, 5, 41, 22 };
    int edge[] = { 0, INT_MAX, -1, INT_MIN, 0 };
    size_t n = sizeof a / sizeof a[0];

    print_array("earlier than:", a, n);
    make_heap_down(h, n);
    print_array("max-heap:", h, n);
    heap_sort(a, n);
    print_array("sorted:", a, n);
    heap_sort_floyd(b, n);
    print_array("floyd:", b, n);
    heap_sort(edge, 5);
    print_array("limits:", edge, 5);
    heap_sort(NULL, 0);                      /* empty: no loop runs */
    return 0;
}

Output:

earlier than:    29 10 14 37 13 5 41 22
max-heap:  41 37 29 22 13 5 14 10
sorted:    5 10 13 14 22 29 37 41
floyd:     5 10 13 14 22 29 37 41
limits:    -2147483648 -1 0 0 2147483647

The small print that carry the correctness:

• youngster >= n is checked earlier than any youngster is learn. The second youngster is learn provided that youngster + 1 < n.
• The construct loop is for (size_t i = n / 2; i-- > 0; ). It visits n/2 − 1 all the way down to 0 with out computing n/2 − 1 for small n and with out an unsigned i >= 0 take a look at. Each of these are errors proven beneath.
• Sift-down is a loop, not recursion, so heap kind wants no stack past a couple of variables.
• Equal kids: SORT_LESS(a[child], a[child + 1]) picks the suitable youngster solely when it’s strictly bigger. Both alternative could be right; this one saves a swap on ties.

Constructing a Heap: Backside-Up vs One Insertion at a Time

There are two methods to show an array right into a heap. make_heap_down() sifts down every mum or dad from the final one again to the foundation; make_heap_up() treats the array as a stream of insertions and sifts every new ingredient up. The counting program measured each:

Output:

constructing a heap: comparisons (and per ingredient)
enter                n       bottom-up (down)         insertion (up)
random           10000         18848 ( 1.88)         22946 ( 2.29)
sorted           10000         19982 ( 2.00)        113631 (11.36)
reversed         10000          9999 ( 1.00)          9999 ( 1.00)
10 distinct      10000         18108 ( 1.81)         19900 ( 1.99)
random         1000000       1881471 ( 1.88)       2282710 ( 2.28)
sorted         1000000       1999974 ( 2.00)      17951445 (17.95)
reversed       1000000        999999 ( 1.00)        999999 ( 1.00)
10 distinct    1000000       1816919 ( 1.82)       1995276 ( 2.00)

sorting n = 10000: comparisons; n log2 n = 132877
enter             heap_sort heap_sort_floyd
random               235343         138789
sorted               244460         142497
reversed             226682         131029
10 distinct          217379         138448

The underside-up construct by no means wanted greater than 2.00 comparisons per ingredient, at 10,000 or at 1,000,000 parts. That’s the O(n) certain: most nodes are close to the underside of the tree, the place a sift-down is brief. Constructing by insertion reached 11.36 comparisons per ingredient at 10,000 and 17.95 at 1,000,000 on sorted enter, the place each new ingredient is the most important up to now and climbs all the best way to the foundation. That’s the O(n log n) case, rising with log₂ n. On random enter the insertion construct was far cheaper, 2.28 comparisons per ingredient at each sizes, as a result of a random new ingredient often stops inside a stage or two. Its worst case is the entire distinction between the 2 strategies.

The construct is a small a part of heap kind’s complete: 18,848 of the 235,343 comparisons on the random 10,000-element enter.

Floyd’s Variant: 41% Fewer Comparisons

The second desk above compares the usual kind with heap_sort_floyd(). The usual sift-down makes two comparisons per stage: one to choose the bigger youngster, one to examine whether or not the ingredient has reached its place. However the ingredient being sifted is the one simply taken from the top of the heap, which is nearly all the time small, so it practically all the time goes to the underside. Floyd’s variant skips the second comparability on the best way down: it strikes the bigger youngster up at each stage till it reaches a leaf, then climbs again as much as the ingredient’s place, often a stage or two.

On 10,000 random values that minimize comparisons from 235,343 to 138,789, a 41% saving that brings heap kind inside about 4% of n log₂ n = 132,877. The time saving was smaller, and it trusted the compiler, as the following part reveals. For int values a comparability is affordable; the variant pays off extra when comparisons are costly, similar to strings or information in contrast by a operate.

How This Was Measured

No CPU pinning or frequency-scaling management was used, no {hardware} counters have been learn, and all timings come from this one digital machine.

Heap Type vs Quicksort as n Grows

One run of the timing program constructed with GCC:

Output:

ms, random ints, median of 5
         n   heap kind       floyd   quicksort  heap / fast
     10000        0.85        0.74        0.64         1.33x
    100000       11.27       10.16        8.18         1.38x
   1000000      148.39      131.35       99.44         1.49x
  10000000     2126.23     1961.47     1106.10         1.92x

Throughout three runs per compiler, the ratio of heap kind’s time to quicksort’s:

Two findings:

• Heap kind fell additional behind quicksort because the array grew, underneath each compilers. At 10,000 parts (40 KB of ints) the ratio was at most 1.33; at 10,000,000 (40 MB) it was a minimum of 1.67. Each algorithms make O(n log n) comparisons, and heap kind’s depend isn’t a lot larger. The likeliest clarification is reminiscence entry: a sift-down from index i subsequent reads 2i + 1, so in a big heap every step down the tree jumps to part of the array that’s not in cache, whereas quicksort’s partition scans the array so as. That’s an inference from the development; no cache-miss counters have been learn.
• Floyd’s variant was sooner with GCC and never with Clang. GCC’s construct ran 8–14% sooner at each dimension. Clang’s construct of the usual model was already sooner than GCC’s, and its Floyd construct was no sooner and typically slower. The 41% comparability saving didn’t develop into a constant time saving for int values.

Three Heap Index Errors

1. The 1-Based mostly Little one Components on a 0-Based mostly Array

Many textbooks retailer the heap from index 1, the place the youngsters of i are 2i and 2i + 1. Used on a C array that begins at 0, the formulation makes index 0 its personal youngster and skips index 1’s actual kids. The outcome can nonetheless look proper:

/* one_based.c - the 1-based youngster formulation 2i and 2i + 1 on a 0-based array */
#embody <stdio.h>
#embody <stddef.h>

static void sift_down_1based(int a[], size_t root, size_t n)
{
    for (;;) {
        size_t youngster = 2 * root;             /* proper for a[1..n], mistaken for a[0..n) */
        if (child >= n)
            return;
        if (child + 1 < n && a[child] < a[child + 1])
            youngster++;
        if (!(a[root] < a[child]))
            return;
        int t = a[root]; a[root] = a[child]; a[child] = t;
        root = youngster;
    }
}

static void heap_sort_1based(int a[], size_t n)
{
    for (size_t i = n / 2; i-- > 0; )
        sift_down_1based(a, i, n);
    for (size_t finish = n; finish > 1; end--) {
        int t = a[0]; a[0] = a[end - 1]; a[end - 1] = t;
        sift_down_1based(a, 0, finish - 1);
    }
}

static void present(const char *label, const int a[], size_t n)
{
    printf("%s", label);
    for (size_t i = 0; i < n; i++)
        printf(" %d", a[i]);
    printf("n");
}

int most important(void)
{
    int a[] = { 29, 10, 14, 37, 13, 5, 41, 22 };   /* the article's instance */
    int b[] = { 45, 9, 84, 35, 95 };               /* discovered by random search */
    heap_sort_1based(a, 8);
    heap_sort_1based(b, 5);
    present("instance:", a, 8);
    present("different:  ", b, 5);
    return 0;
}

Output (GCC and Clang, an identical):

instance: 5 10 13 14 22 29 37 41
different:   9 35 45 95 84

The article’s instance got here out sorted. The second enter, 45 9 84 35 95, didn’t: 95 and 84 are within the mistaken order. A search program within the repository sorted 100,000 random arrays of two to 16 values with the identical operate:

8651 of 100000 random arrays not sorted

It failed on 8.7% of them. A bug that passes the instance used to develop it and fails one time in twelve on random enter is the type a take a look at suite of some hand-written circumstances won’t discover. Check a kind in opposition to a reference on hundreds of random inputs, because the repository’s exams do.

2. An Unsigned Construct Loop

The construct loop is usually written for (i = n / 2 - 1; i >= 0; i--). With a size_t index, i >= 0 is all the time true:

/* unsigned_build.c - the textbook construct loop with a size_t index */
#embody <stdio.h>
#embody <stddef.h>

static void sift_down(int a[], size_t root, size_t n)
{
    for (;;) {
        size_t youngster = 2 * root + 1;
        if (youngster >= n)
            return;
        if (youngster + 1 < n && a[child] < a[child + 1])
            youngster++;
        if (!(a[root] < a[child]))
            return;
        int t = a[root]; a[root] = a[child]; a[child] = t;
        root = youngster;
    }
}

int most important(void)
{
    int a[] = { 29, 10, 14, 37, 13, 5, 41, 22 };
    size_t n = sizeof a / sizeof a[0];
    for (size_t i = n / 2 - 1; i >= 0; i--)  /* i >= 0 is all the time true */
        sift_down(a, i, n);
    printf("heap constructed: %dn", a[0]);
    return 0;
}

GCC’s -Wextra flags it; Clang 18’s -Wall -Wextra printed no warning:

unsigned_build.c:24:34: warning: comparability of unsigned expression in '>= 0' is all the time true [-Wtype-limits]

This model doesn’t crash. After i wraps previous zero to SIZE_MAX, 2 * i + 1 additionally wraps, to a worth far above n, so sift_down() returns directly with out touching reminiscence. The loop then counts down by about 2⁶⁴ values doing nothing. The GCC and Clang builds at -O2, a GCC construct at -O0, and a construct with AddressSanitizer and UndefinedBehaviorSanitizer all printed nothing and have been nonetheless working when stopped after 20 seconds. The sanitizers had nothing to report: no reminiscence was accessed out of bounds, and unsigned wraparound is outlined habits. This system seems hung, not damaged. The identical expression additionally fails a second approach: for n of 0 or 1, n / 2 - 1 is itself SIZE_MAX.

3. youngster <= n As an alternative of youngster < n

An off-by-one within the certain lets sift_down() deal with a[n], one ingredient previous the heap, as a toddler:

/* child_bound.c - "youngster <= n" as an alternative of "youngster < n" in sift_down */
#embody <stdio.h>
#embody <stddef.h>

static void sift_down(int a[], size_t root, size_t n)
{
    for (;;) {
        size_t youngster = 2 * root + 1;
        if (youngster > n)                       /* needs to be youngster >= n */
            return;
        if (youngster + 1 <= n && a[child] < a[child + 1])
            youngster++;
        if (!(a[root] < a[child]))
            return;
        int t = a[root]; a[root] = a[child]; a[child] = t;
        root = youngster;
    }
}

int most important(void)
{
    int a[] = { 29, 10, 14, 37, 13, 5, 41, 22 };
    size_t n = sizeof a / sizeof a[0];
    for (size_t i = n / 2; i-- > 0; )
        sift_down(a, i, n);
    for (size_t finish = n; finish > 1; end--) {
        int t = a[0]; a[0] = a[end - 1]; a[end - 1] = t;
        sift_down(a, 0, finish - 1);
    }
    for (size_t i = 0; i < n; i++)
        printf("%d ", a[i]);
    printf("n");
    return 0;
}

In the course of the construct, a[n] is previous the top of the array itself. The outcomes over repeated runs:

When the worth previous the top is bigger than the foundation, the swap writes the foundation outdoors the array and brings the surface worth in. What that worth is is determined by what the stack holds, which is why the Clang construct printed a distinct quantity every time. The loop certain should be youngster < n, and the right-child take a look at youngster + 1 < n.

Heap Type Time and Area Complexity

Heap Type in C++, Java, Python and C#

C++

The template kinds any random-access vary with a comparator; the heap is a max-heap with respect to comp, so std::larger<>{} offers descending order. The demo additionally makes use of the usual library’s heap instruments:

// heap_sort.hpp - generic heap kind for C++17
#ifndef HEAP_SORT_HPP
#outline HEAP_SORT_HPP

#embody <purposeful>
#embody <iterator>
#embody <utility>

namespace element {

template <class RandomIt, class Diff, class Evaluate>
void sift_down(RandomIt first, Diff root, Diff n, Evaluate& comp)
{
    for (;;) {
        Diff youngster = 2 * root + 1;
        if (youngster >= n)
            return;
        if (youngster + 1 < n && comp(first[child], first[child + 1]))
            ++youngster;                                  // the bigger youngster
        if (!comp(first[root], first[child]))
            return;
        std::iter_swap(first + root, first + youngster);
        root = youngster;
    }
}

}  // namespace element

// In place, O(n log n) worst case, not steady. comp(a, b) means "a goes
// earlier than b"; the heap is a max-heap with respect to comp.
template <class RandomIt, class Evaluate = std::much less<>>
void heap_sort(RandomIt first, RandomIt final, Evaluate comp = {})
{
    utilizing Diff = typename std::iterator_traits<RandomIt>::difference_type;
    Diff n = final - first;
    for (Diff i = n / 2; i-- > 0; )                   // construct the heap
        element::sift_down(first, i, n, comp);
    for (Diff finish = n; finish > 1; --end) {              // extract the most important
        std::iter_swap(first, first + (finish - 1));
        element::sift_down(first, Diff{0}, finish - 1, comp);
    }
}

#endif

// heap_demo.cpp - the generic heap kind, and the usual library's heap instruments
#embody <algorithm>
#embody <purposeful>
#embody <iostream>
#embody <queue>
#embody <string>
#embody <vector>
#embody "heap_sort.hpp"

template <class Vary>
void print(const char* label, const Vary& r)
{
    std::cout << label;
    for (const auto& x : r) std::cout << ' ' << x;
    std::cout << 'n';
}

int most important()
{
    std::vector<int> v{29, 10, 14, 37, 13, 5, 41, 22};
    heap_sort(v.start(), v.finish());
    print("heap_sort:        ", v);

    heap_sort(v.start(), v.finish(), std::larger<>{});
    print("descending:       ", v);

    std::vector<std::string> phrases{"pear", "fig", "apple", "kiwi", "date"};
    heap_sort(phrases.start(), phrases.finish());
    print("strings:          ", phrases);

    std::vector<int> w{29, 10, 14, 37, 13, 5, 41, 22};
    std::make_heap(w.start(), w.finish());               // the identical max-heap structure
    print("std::make_heap:   ", w);
    std::sort_heap(w.start(), w.finish());
    print("std::sort_heap:   ", w);

    std::vector<int> ok{29, 10, 14, 37, 13, 5, 41, 22};
    std::partial_sort(ok.start(), ok.start() + 3, ok.finish());   // three smallest, sorted
    std::cout << "partial_sort, 3:   " << ok[0] << ' ' << ok[1] << ' ' << ok[2] << 'n';

    std::vector<int> q{29, 10, 14, 37, 13, 5, 41, 22};
    std::priority_queue<int> pq(q.start(), q.finish());      // a max-heap beneath
    std::cout << "priority_queue:   ";
    whereas (!pq.empty()) { std::cout << ' ' << pq.high(); pq.pop(); }
    std::cout << 'n';
    return 0;
}

Output (g++ 13.3 and clang++ 18.1.3 with libstdc++, an identical):

heap_sort:         5 10 13 14 22 29 37 41
descending:        41 37 29 22 14 13 10 5
strings:           apple date fig kiwi pear
std::make_heap:    41 37 29 22 13 5 14 10
std::sort_heap:    5 10 13 14 22 29 37 41
partial_sort, 3:   5 10 13
priority_queue:    41 37 29 22 14 13 10 5

std::make_heap produced precisely the structure make_heap_down() produced in C, 41 37 29 22 13 5 14 10. The C++ commonplace requires a legitimate heap, not a specific one, so one other commonplace library might print a distinct line there. std::sort_heap on that heap is the second half of heap kind. std::partial_sort finds the ok smallest parts so as, which libstdc++ implements with a heap of dimension ok, and std::priority_queue is a max-heap on a std::vector with push and pop in O(log n).

Java

// HeapSort.java - heap kind in Java 21
import java.util.Arrays;

public class HeapSort {

    // Max-heap within the array: kids of i at 2i + 1 and 2i + 2. Not steady.
    static void heapSort(int[] a) {
        int n = a.size;
        for (int i = n / 2 - 1; i >= 0; i--)     // int index: i >= 0 is an actual take a look at
            siftDown(a, i, n);
        for (int finish = n - 1; finish > 0; end--) {
            int t = a[0]; a[0] = a[end]; a[end] = t;
            siftDown(a, 0, finish);
        }
    }

    non-public static void siftDown(int[] a, int root, int n) {
        whereas (true) {
            int youngster = 2 * root + 1;
            if (youngster >= n)
                return;
            if (youngster + 1 < n && a[child] < a[child + 1])
                youngster++;
            if (a[root] >= a[child])
                return;
            int t = a[root]; a[root] = a[child]; a[child] = t;
            root = youngster;
        }
    }

    public static void most important(String[] args) {
        int[] information = {29, 10, 14, 37, 13, 5, 41, 22};
        heapSort(information);
        System.out.println("Sorted: " + Arrays.toString(information));
    }
}

Sorted: [5, 10, 13, 14, 22, 29, 37, 41]

Java has no unsigned int, so the i >= 0 loop that hangs in C with size_t is right right here. For a heap as an information construction, java.util.PriorityQueue is a min-heap by default.

Python

"""Heap kind in Python 3."""


def sift_down(a: listing[int], root: int, n: int) -> None:
    """Transfer a[root] down the max-heap a[0:n] till neither youngster is bigger."""
    whereas True:
        youngster = 2 * root + 1
        if youngster >= n:
            return
        if youngster + 1 < n and a[child] < a[child + 1]:
            youngster += 1
        if not a[root] < a[child]:
            return
        a[root], a[child] = a[child], a[root]
        root = youngster


def heap_sort(a: listing[int]) -> listing[int]:
    """Type listing a in place. O(n log n) worst case, not steady."""
    n = len(a)
    for i in vary(n // 2 - 1, -1, -1):
        sift_down(a, i, n)
    for finish in vary(n - 1, 0, -1):
        a[0], a[end] = a[end], a[0]
        sift_down(a, 0, finish)
    return a


if __name__ == "__main__":
    information = [29, 10, 14, 37, 13, 5, 41, 22]
    print("Sorted:", heap_sort(information))

Sorted: [5, 10, 13, 14, 22, 29, 37, 41]

The usual library’s heapq module maintains a min-heap in an extraordinary listing. heapq.heapify() on the instance array offers [5, 10, 14, 22, 13, 29, 41, 37], and heapq.nsmallest(3, …) returns [5, 10, 13].

C#

// HeapSort.cs - heap kind in C#
namespace MyCPlus.Sorting;

public static class HeapSort
{
    // Max-heap within the array: kids of i at 2i + 1 and 2i + 2. Not steady.
    public static void Type(int[] a)
    {
        int n = a.Size;
        for (int i = n / 2 - 1; i >= 0; i--)
            SiftDown(a, i, n);
        for (int finish = n - 1; finish > 0; end--)
        {
            int t = a[0]; a[0] = a[end]; a[end] = t;
            SiftDown(a, 0, finish);
        }
    }

    non-public static void SiftDown(int[] a, int root, int n)
    {
        whereas (true)
        {
            int youngster = 2 * root + 1;
            if (youngster >= n)
                return;
            if (youngster + 1 < n && a[child] < a[child + 1])
                youngster++;
            if (a[root] >= a[child])
                return;
            int t = a[root]; a[root] = a[child]; a[child] = t;
            root = youngster;
        }
    }
}

// Program.cs - kinds the article's array with HeapSort.Type
utilizing System;

namespace MyCPlus.Sorting;

public static class Program
{
    public static void Fundamental()
    {
        int[] information = { 29, 10, 14, 37, 13, 5, 41, 22 };
        HeapSort.Type(information);
        Console.WriteLine("Sorted: [" + string.Join(", ", data) + "]");
    }
}

Sorted: [5, 10, 13, 14, 22, 29, 37, 41]

The place Heap Type Is Used

In libstdc++ 13, std::kind‘s introsort loop calls __partial_sort, a heap kind, as soon as the depth restrict is reached. OpenJDK 21’s DualPivotQuicksort switches to its personal heapSort when the recursion depth passes a restrict.

Key Takeaways

• A heap is an array with an index rule. Kids of i at 2i + 1 and 2i + 2 for 0-based arrays; the 1-based formulation failed on 8.7% of random inputs whereas sorting the instance accurately.
• Construct the heap bottom-up. At most 2 comparisons per ingredient, in opposition to as much as 17.95 per ingredient for repeated insertion on sorted enter.
• Heap kind’s comparability depend barely is determined by the enter: 217,379 to 244,460 for 10,000 values throughout 4 preparations.
• Floyd’s variant saves about 41% of comparisons, which saved 8–14% of the time with GCC and nothing in keeping with Clang for int values.
• Heap kind loses floor to quicksort as n grows: as much as 1.5× slower as much as 1,000,000 parts, 1.7–2.1× at ten million on this machine.
• Index bugs in heap code fail quietly. An unsigned construct loop hung with no sanitizer report; an off-by-one certain printed intact however unsorted output underneath GCC and pulled outdoors values into the array underneath Clang.

Incessantly Requested Questions

Conclusion

Heap kind is the algorithm that makes each assure the others lack: in place, no recursion, no unhealthy enter. The measurements present what these ensures price. Its comparability depend is nearly fixed, however its reminiscence entry sample will get worse as arrays develop, so a kind that’s 1.2 instances slower than quicksort on small arrays is twice as sluggish on giant ones. libstdc++ and OpenJDK each maintain it because the fallback that ensures the worst case, not because the algorithm they run first.

The heap itself outlives heap kind. Precedence queues, top-k choice and schedulers all run on the identical array structure and the identical two operations, sift up and sift down. For the opposite algorithms on this collection and the way they evaluate, see the algorithms part.

Supply Code and Assessments

The C code is in mycplus/c-examples/sorting/heap-sort and the C++ code in mycplus/cpp-examples/sorting/heap-sort . The Java, Python and C# variations are in mycplus/java-examples/sorting/heap-sort, mycplus/python-examples/sorting/heap-sort and mycplus/csharp-examples/sorting/heap-sort, every with its personal exams and workflow.

Construct and take a look at both one with:

cmake -S . -B construct
cmake --build construct
ctest --test-dir construct --output-on-failure

What the builds examine on every change:

• Compilation with warnings as errors: GCC and Clang with -Wall -Wextra -pedantic -Werror (C11 and C17; C++17 and C++20), and MSVC with /W4 /WX.
• Correctness in opposition to a reference: each C kinds in opposition to qsort(), and each heap builds for the heap property, on 20,000 random arrays of 0 to 64 parts together with empty arrays, INT_MIN, INT_MAX and heavy duplication; the C++ template in opposition to std::kind on 5,000 inputs, ascending and descending.
• The output on this web page: the instance, the hint, the depend tables, the 1-based pitfall and its random search, and the C++ demo (with libstdc++) are in contrast with the output blocks above.
• Sanitizers: all exams run once more underneath AddressSanitizer and UndefinedBehaviorSanitizer.
• The pitfalls: the construct confirms that GCC warns concerning the unsigned construct loop and that this system runs till stopped, and that AddressSanitizer stories the youngster <= n learn.

The builds don’t run the timing program, which is determined by the machine. A inexperienced badge means the code compiles on these toolchains and passes these exams; it doesn’t reproduce the timings above.