Code Coverage
 
Lines
Functions and Methods
Classes and Traits
Total
100.00% covered (success)
100.00%
24 / 24
100.00% covered (success)
100.00%
2 / 2
 CRAP
100.00% covered (success)
100.00%
1 / 1
HeapSort
100.00% covered (success)
100.00%
24 / 24
100.00% covered (success)
100.00%
2 / 2
 11
100.00% covered (success)
100.00%
1 / 1
 __construct
n/a
0 / 0
n/a
0 / 0
 1
 sort
100.00% covered (success)
100.00%
13 / 13
100.00% covered (success)
100.00%
1 / 1
 4
 heapify
100.00% covered (success)
100.00%
11 / 11
100.00% covered (success)
100.00%
1 / 1
 6
1<?php
2/**
3 * Jingga
4 *
5 * PHP Version 8.1
6 *
7 * @package   phpOMS\Algorithm\Sort;
8 * @copyright Dennis Eichhorn
9 * @license   OMS License 2.0
10 * @version   1.0.0
11 * @link      https://jingga.app
12 */
13declare(strict_types=1);
14
15namespace phpOMS\Algorithm\Sort;
16
17/**
18 * HeapSort class.
19 *
20 * @package phpOMS\Algorithm\Sort;
21 * @license OMS License 2.0
22 * @link    https://jingga.app
23 * @since   1.0.0
24 */
25final class HeapSort implements SortInterface
26{
27    /**
28     * Constructor
29     *
30     * @since 1.0.0
31     * @codeCoverageIgnore
32     */
33    private function __construct()
34    {
35    }
36
37    /**
38     * {@inheritdoc}
39     */
40    public static function sort(array $list, int $order = SortOrder::ASC) : array
41    {
42        $n = \count($list);
43
44        if ($n < 2) {
45            return $list;
46        }
47
48        $copy = $list;
49
50        for ($p = (int) ($n / 2 - 1); $p >= 0; --$p) {
51            self::heapify($copy, $n, $p, $order);
52        }
53
54        for ($i = $n - 1; $i > 0; --$i) {
55            $temp     = $copy[$i];
56            $copy[$i] = $copy[0];
57            $copy[0]  = $temp;
58
59            --$n;
60            self::heapify($copy, $n, 0, $order);
61        }
62
63        return $copy;
64    }
65
66    /**
67     * Convert into heap data structure
68     *
69     * @param array $list  Data to sort
70     * @param int   $size  Heap size
71     * @param int   $index Index element
72     * @param int   $order Sort order
73     *
74     * @return void
75     *
76     * @since 1.0.0
77     */
78    private static function heapify(array &$list, int $size, int $index, int $order) : void
79    {
80        $left  = ($index + 1) * 2 - 1;
81        $right = ($index + 1) * 2;
82        $pivot = 0;
83
84        $pivot = $left < $size && $list[$left]->compare($list[$index], $order) ? $left : $index;
85
86        if ($right < $size && $list[$right]->compare($list[$pivot], $order)) {
87            $pivot = $right;
88        }
89
90        if ($pivot !== $index) {
91            $temp         = $list[$index];
92            $list[$index] = $list[$pivot];
93            $list[$pivot] = $temp;
94
95            self::heapify($list, $size, $pivot, $order);
96        }
97    }
98}