https://ru.wikibooks.org/wiki/Реализации_алгоритмов/Сортировка/Пирамидальная#Java
Уровень абстракции 0 (Исходный код)
(Оффтоп)
Код:
/**
* Класс для сортировки массива целых чисел с помощью кучи.
* Методы в классе написаны в порядке их использования. Для сортировки
* вызывается статический метод sort(int[] a)
*/
class HeapSort {
/**
* Размер кучи. Изначально равен размеру сортируемого массива
*/
private static int heapSize;
/**
* Сортировка с помощью кучи.
* Сначала формируется куча:
* @see HeapSort#buildHeap(int[])
* Теперь максимальный элемент массива находится в корне кучи. Его нужно
* поменять местами с последним элементом и убрать из кучи (уменьшить
* размер кучи на 1). Теперь в корне кучи находится элемент, который раньше
* был последним в массиве. Нужно переупорядочить кучу так, чтобы
* выполнялось основное условие кучи - a[parent]>=a[child]:
* @see #heapify(int[], int)
* После этого в корне окажется максимальный из оставшихся элементов.
* Повторить до тех пор, пока в куче не останется 1 элемент
*
* @param a сортируемый массив
*/
public static void sort(int[] a) {
buildHeap(a);
while (heapSize > 1) {
swap(a, 0, heapSize - 1);
heapSize--;
heapify(a, 0);
}
}
/**
* Построение кучи. Поскольку элементы с номерами начиная с a.length / 2 + 1
* это листья, то нужно переупорядочить поддеревья с корнями в индексах
* от 0 до a.length / 2 (метод heapify вызывать в порядке убывания индексов)
*
* @param a - массив, из которого формируется куча
*/
private static void buildHeap(int[] a) {
heapSize = a.length;
for (int i = a.length / 2; i >= 0; i--) {
heapify(a, i);
}
}
/**
* Переупорядочивает поддерево кучи начиная с узла i так, чтобы выполнялось
* основное свойство кучи - a[parent] >= a[child].
*
* @param a - массив, из которого сформирована куча
* @param i - корень поддерева, для которого происходит переупорядочивание
*/
private static void heapify(int[] a, int i) {
int l = left(i);
int r = right(i);
int largest = i;
if (l < heapSize && a[i] < a[l]) {
largest = l;
}
if (r < heapSize && a[largest] < a[r]) {
largest = r;
}
if (i != largest) {
swap(a, i, largest);
heapify(a, largest);
}
}
/**
* Возвращает индекс правого потомка текущего узла
*
* @param i индекс текущего узла кучи
* @return индекс правого потомка
*/
private static int right(int i) {
return 2 * i + 2;
}
/**
* Возвращает индекс левого потомка текущего узла
*
* @param i индекс текущего узла кучи
* @return индекс левого потомка
*/
private static int left(int i) {
return 2 * i + 1;
}
/**
* Меняет местами два элемента в массиве
*
* @param a массив
* @param i индекс первого элемента
* @param j индекс второго элемента
*/
private static void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
Уровень абстракции 1 (убраны комментарии)
(Оффтоп)
Код:
class HeapSort {
private static int heapSize;
public static void sort(int[] a) {
buildHeap(a);
while (heapSize > 1) {
swap(a, 0, heapSize - 1);
heapSize--;
heapify(a, 0);
}
}
private static void buildHeap(int[] a) {
heapSize = a.length;
for (int i = a.length / 2; i >= 0; i--) {
heapify(a, i);
}
}
private static void heapify(int[] a, int i) {
int l = left(i);
int r = right(i);
int largest = i;
if (l < heapSize && a[i] < a[l]) {
largest = l;
}
if (r < heapSize && a[largest] < a[r]) {
largest = r;
}
if (i != largest) {
swap(a, i, largest);
heapify(a, largest);
}
}
private static int right(int i) {
return 2 * i + 2;
}
private static int left(int i) {
return 2 * i + 1;
}
private static void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
Уровень абстракции 2 (убраны атрибуты методов)
(Оффтоп)
Код:
class HeapSort {
int heapSize;
void sort(int[] a) {
buildHeap(a);
while (heapSize > 1) {
swap(a, 0, heapSize - 1);
heapSize--;
heapify(a, 0);
}
}
void buildHeap(int[] a) {
heapSize = a.length;
for (int i = a.length / 2; i >= 0; i--) {
heapify(a, i);
}
}
void heapify(int[] a, int i) {
int l = left(i);
int r = right(i);
int largest = i;
if (l < heapSize && a[i] < a[l]) {
largest = l;
}
if (r < heapSize && a[largest] < a[r]) {
largest = r;
}
if (i != largest) {
swap(a, i, largest);
heapify(a, largest);
}
}
int right(int i) {
return 2 * i + 2;
}
int left(int i) {
return 2 * i + 1;
}
void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
Уровень абстракции 3 (убраны типы данных)
(Оффтоп)
Код:
class HeapSort {
heapSize;
void sort(a) {
buildHeap(a);
while (heapSize > 1) {
swap(a, 0, heapSize - 1);
heapSize--;
heapify(a, 0);
}
}
void buildHeap(a) {
heapSize = a.length;
for (i = a.length / 2; i >= 0; i--) {
heapify(a, i);
}
}
void heapify(a, i) {
l = left(i);
r = right(i);
largest = i;
if (l < heapSize && a[i] < a[l]) {
largest = l;
}
if (r < heapSize && a[largest] < a[r]) {
largest = r;
}
if (i != largest) {
swap(a, i, largest);
heapify(a, largest);
}
}
right(i) {
return 2 * i + 2;
}
left(i) {
return 2 * i + 1;
}
void swap(a, i, j) {
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
Уровень абстракции 4 (условия из if, циклов for и while, выражений в присвоениях и аргументы в вызовах методов заменены на сигнатуры abstract-функций)
(Оффтоп)
Код:
class HeapSort {
heapSize;
void sort(a) {
buildHeap(a);
while (abstract(heapSize)) {
swap(abstract(a, heapSize));
heapSize--;
heapify(abstract(a));
}
}
void buildHeap(a) {
heapSize = abstract(a);
for (i = abstract(a)) {
heapify(a, i);
}
}
void heapify(a, i) {
l = left(i);
r = right(i);
largest = i;
if (abstract(l, heapSize, a[i], a[l])) {
largest = l;
}
if (abstract(r, heapSize, a[largest], a[r])) {
largest = r;
}
if (abstract(i, largest)) {
swap(a, i, largest);
heapify(a, largest);
}
}
right(i) {
return abstract(i);
}
left(i) {
return abstract(i);
}
void swap(a, i, j) {
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
Уровень абстракции 4.1 (схлопывание тривиальных языковых конструкций return ...)
(Оффтоп)
Код:
class HeapSort {
heapSize;
void sort(a) {
buildHeap(a);
while (abstract(heapSize)) {
swap(abstract(a, heapSize));
heapSize--;
heapify(abstract(a));
}
}
void buildHeap(a) {
heapSize = abstract(a);
for (i = abstract(a)) {
heapify(a, i);
}
}
void heapify(a, i) {
l = left(i);
r = right(i);
largest = i;
if (abstract(l, heapSize, a[i], a[l])) {
largest = l;
}
if (abstract(r, heapSize, a[largest], a[r])) {
largest = r;
}
if (abstract(i, largest)) {
swap(a, i, largest);
heapify(a, largest);
}
}
right(i) {...}
left(i) {...}
void swap(a, i, j) {
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
Уровень абстракции 5 (замена локальных переменных в методах, циклах for, abstract-функциях на abstract-функцию)
(Оффтоп)
Код:
class HeapSort {
heapSize;
void sort(a) {
buildHeap(a);
while (abstract(heapSize)) {
swap(abstract(a, heapSize));
heapSize--;
heapify(abstract(a));
}
}
void buildHeap(a) {
heapSize = abstract(a);
for (abstract(a)) {
heapify(abstract(a));
}
}
void heapify(a, i) {
l = left(i);
r = right(i);
largest = i;
if (abstract(abstract(i), heapSize, a[i], a[abstract(i)])) {
largest = abstract(i);
}
if (abstract(abstract(i), heapSize, a[abstract(i)], a[abstract(i)])) {
largest = abstract(i);
}
if (abstract(i, abstract(i))) {
swap(a, i, abstract(i));
heapify(a, abstract(i));
}
}
right(i) {...}
left(i) {...}
void swap(a, i, j) {
temp = a[i];
a[i] = a[j];
a[j] = abstract(a[i]);
}
}
Уровень абстракции 5.1 (схлопывание вложенных abstract-функций, правые части присвоения локальных переменных заменены на многоточие)
(Оффтоп)
Код:
class HeapSort {
heapSize;
void sort(a) {
buildHeap(a);
while (abstract(heapSize)) {
swap(abstract(a, heapSize));
heapSize--;
heapify(abstract(a));
}
}
void buildHeap(a) {
heapSize = abstract(a);
for (abstract(a)) {
heapify(abstract(a));
}
}
void heapify(a, i) {
l = ...;
r = ...;
largest = ...;
if (abstract(i, heapSize, a)) {
largest = ...;
}
if (abstract(i, heapSize, a)) {
largest = ...;
}
if (abstract(i)) {
swap(abstract(a, i));
heapify(abstract(a, i));
}
}
right(i) {...}
left(i) {...}
void swap(a, i, j) {
temp = ...;
a[i] = a[j];
a[j] = abstract(a[i]);
}
}
Уровень абстракции 5.2 (присвоения локальных переменных целиком заменены на многоточие, «неиспользуемые» методы left() и right() заменены на многоточия)
(Оффтоп)
Код:
class HeapSort {
heapSize;
void sort(a) {
buildHeap(a);
while (abstract(heapSize)) {
swap(abstract(a, heapSize));
heapSize--;
heapify(abstract(a));
}
}
void buildHeap(a) {
heapSize = abstract(a);
for (abstract(a)) {
heapify(abstract(a));
}
}
void heapify(a, i) {
...;
if (abstract(i, heapSize, a)) {
...;
}
if (abstract(i, heapSize, a)) {
...;
}
if (abstract(i)) {
swap(abstract(a, i));
heapify(abstract(a, i));
}
}
...() {...}
...() {...}
void swap(a, i, j) {
...;
a[i] = a[j];
a[j] = abstract(a[i]);
}
}
Уровень абстракции 6 (условия из if, циклов for и while заменены на многоточие)
(Оффтоп)
Код:
class HeapSort {
heapSize;
void sort(a) {
buildHeap(a);
while (...) {
swap(abstract(a, heapSize));
heapSize--;
heapify(abstract(a));
}
}
void buildHeap(a) {
heapSize = abstract(a);
for (...) {
heapify(abstract(a));
}
}
void heapify(a, i) {
...;
if (...) {
...;
}
if (...) {
...;
}
if (...) {
swap(abstract(a, i));
heapify(abstract(a, i));
}
}
...() {...}
...() {...}
void swap(a, i, j) {
...;
a[i] = a[j];
a[j] = abstract(a[i]);
}
}
Уровень абстракции 6.1 (схлопывание тривиальных инструкций if)
(Оффтоп)
Код:
class HeapSort {
heapSize;
void sort(a) {
buildHeap(a);
while (...) {
swap(abstract(a, heapSize));
heapSize--;
heapify(abstract(a));
}
}
void buildHeap(a) {
heapSize = abstract(a);
for (...) {
heapify(abstract(a));
}
}
void heapify(a, i) {
...;
if (...) {
swap(abstract(a, i));
heapify(abstract(a, i));
}
}
...() {...}
...() {...}
void swap(a, i, j) {
...;
a[i] = a[j];
a[j] = abstract(a[i]);
}
}
Уровень абстракции 7 (имена аргументов в вызовах методов и abstract-функций заменены на многоточие)
(Оффтоп)
Код:
class HeapSort {
heapSize;
void sort(a) {
buildHeap(...);
while (...) {
swap(...);
heapSize--;
heapify(...);
}
}
void buildHeap(a) {
heapSize = abstract(...);
for (...) {
heapify(...);
}
}
void heapify(a, i) {
...;
if (...) {
swap(abstract(...));
heapify(abstract(...));
}
}
...() {...}
...() {...}
void swap(a, i, j) {
...;
a[i] = ...;
a[j] = abstract(...);
}
}
Уровень абстракции 7.1 (abstract-функции заменены на многоточие)
(Оффтоп)
Код:
class HeapSort {
heapSize;
void sort(a) {
buildHeap(...);
while (...) {
swap(...);
heapSize--;
heapify(...);
}
}
void buildHeap(a) {
heapSize = ...;
for (...) {
heapify(...);
}
}
void heapify(a, i) {
...;
if (...) {
swap(...);
heapify(...);
}
}
...() {...}
...() {...}
void swap(a, i, j) {
...;
a[i] = ...;
a[j] = ...;
}
}
Уровень абстракции 8 (инструкции if, for, while заменены на многоточие; фактически получается карта использования функций и присвоений)
(Оффтоп)
Код:
class HeapSort {
heapSize;
void sort(a) {
buildHeap(...);
...;
swap(...);
heapSize = ...;
heapify(...);
}
void buildHeap(a) {
heapSize = ...;
...;
heapify(...);
}
void heapify(a, i) {
...;
swap(...);
heapify(...);
}
...() {...}
...() {...}
void swap(a, i, j) {
...;
a[i] = ...;
a[j] = ...;
}
}
Уровень абстракции 9 (тела методов заменены на многоточие)
(Оффтоп)
Код:
class HeapSort {
heapSize;
void sort(a) {...}
void buildHeap(a) {...}
void heapify(a, i) {...}
...() {...}
...() {...}
void swap(a, i, j) {...}
}
Уровень абстракции 10 (имена аргументов методов заменены на многоточие)
(Оффтоп)
Код:
class HeapSort {
heapSize;
void sort(...) {...}
void buildHeap(...) {...}
void heapify(...) {...}
...() {...}
...() {...}
void swap(...) {...}
}
Уровень абстракции 11 (имена выходных параметров методов заменены на многоточие)
(Оффтоп)
Код:
class HeapSort {
heapSize;
... sort(...) {...}
... buildHeap(...) {...}
... heapify(...) {...}
...() {...}
...() {...}
... swap(...) {...}
}
Уровень абстракции 12 (поля и методы класса заменены на многоточие)
(Оффтоп)
Уровень абстракции 13 (весь код заменен на многоточие, весь код абстрактный)
(Оффтоп)
-- 11.03.2021, 21:16 --К сожалению, форум не позволяет совместить код и оффтопик (спойлер). Советую начать просматривать преобразования с конца (начать с уровня 13).
Порядок преобразований (абстрагирований) не самый оптимальный, но самое главное понять суть.
от переменной 
. Нам неинтересно название функции, ибо зная сигнатуру функции, можно понять, как ей следовало бы называться, более того, имя выходной переменной зачастую совпадает с именем функции, например, getXCoord(). 
в десятеричной или 
в двоичной? Почему?