Куча | java@Cat

В данном отчёте я напишу о структуре данных под названием куча (Heap), а точнее — о её разновидности.

Двоичная куча

Двоичная куча — структура данных, двоичное дерево, для которого выполнены три условия:

Значение в любой вершине не меньше чем значение в потомках
Расстояние до корня отличается не более чем на один уровень
Заполняется слева на право

Зафиксируем операции, которые будем проводить над кучей:

Достать максимальный элемент из кучи, не удаляя его
Добавить элемент в кучу
Создать кучу
Отсортировать массив путём превращения его в кучу, а кучи — в отсортированный массив
Узнать размер кучи
Удалить максимальный элемент из кучи

Описание методов

1. Восстановление свойства кучи

Каждый элемент помещается в конец кучи, потом становится на своё место, соответственно свойств кучи.

Сложность: $O(\log(n))$

2. Возврат максимального элемента

Возвратить содержимое самой верхней вершины.

Сложность: $O(1)$

3. Удаление максимального элемента

Меняются местами первая и последняя вершины, после чего последняя вершина запоминается и удаляется, а новая первая вершина проталкивается в кучу, согласно её свойствам.

Сложность: $O(\log(n))$

4. Пирамидальная сортировка

Достаточно заметить, что в самую первую вершину кучи всегда (по крайней мере, по введённым свойствам) встаёт максимальный элемент. Если каждый раз удалять максимальный элемент — получим отсортированный массив.

Сложность: $O(n\log(n))$

О реализации

Реализуется структура данных с абстрактным типом данных. Для хранения вершин будем использовать ArrayList. Для каждой вершины под номером $i$ её левый сын хранится в $2*i+1$ вершине, а правый — в $2*i+2$ вершине.

Класс содержит следующие методы:

Heap() — конструктор
shiftUp() — восходящее восстановление свойства кучи
shiftDown() — нисходящее восстановление свойства кучи
insert() — добавление элемента в кучу
delete() — удаление первой вершины
size() — размер кучи
isEmpty() — проверка на пустоту
toString() — преобразование в строку
max() — максимальный элемент
print() — вывод кучи на экран

Код

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Heap <T extends Comparable<T> > {
    //arraylist is much better than an array. There is no need to carry about a capacity.
    private ArrayList<T> items;
 
    //construct
    public Heap() {
        items = new ArrayList<T> ();   
    }
 
    //using shiftUp for insert. 
    private void shiftUp () {
        int k = items.size() - 1;
        while (k > 0){
            int curr = (k-1)/2;
            T Item = items.get(k);
            T Parent = items.get(curr);
            if (Item.compareTo(Parent) > 0){
                items.set(k, Parent);
                items.set(curr, Item);
                k = curr;
            }
            else break;
        }
    }
 
    //using shiftDown fo delete
    private void shiftDown() {
        int curr = 0; 
        int leftChild = 2*curr+1;
        while (leftChild < items.size()) {
            int max = leftChild;
            int rightChild = leftChild + 1;
            if (rightChild < items.size()) {
                if (items.get(rightChild).compareTo(items.get(1)) > 0) {
                    ++max;
                }
            }
            if (items.get(curr).compareTo(items.get(max)) < 0) {
                T tmp = items.get(curr);
                items.set(curr, items.get(max));
                items.set(max, tmp);
                curr = max;
                leftChild = 2*curr+1;
            }
            else break;
        }
    }
 
    public void insert(T item) {
        items.add(item);
        shiftUp();
    }
 
    public T delete() throws NoSuchElementException {
        if (items.size() == 0) {
            throw new NoSuchElementException();
        }
        if (items.size() == 1) return items.remove(0);
        T x = items.get(0);
        items.set(0, items.remove(items.size()-1));
        shiftDown();
        return x;
    }
 
    public int size() {
        return items.size();
    }
 
    public boolean isEmpty() {
        return items.isEmpty();
    }
 
    public String toString() {
        return items.toString();
    }
 
    public T max() {
        return items.get(0);
    }
    public void print() {
        for (int i = 0; i < items.size(); i++) {
            System.out.print(items.get(i).toString() + " ");
        }
        System.out.println();
    }
}
 
class Codechef {   
	public static void main (String[] args) {
		Heap <Integer> test = new Heap<Integer> ();
		test.insert(16);
		test.insert(9);
		test.insert(11);
		test.insert(10);
		test.insert(13);
		test.insert(31);
		test.insert(19);
		test.insert(2);
		test.insert(50);
		test.insert(23);
		test.print();
		//To kill some hares in the same time:
		//- isEmpty() works;
		// max() and toString() too
		// so does delete() => shiftDown() works;
		// heapsort :D
		for (;!test.isEmpty();) {
		    System.out.print(test.max().toString() + " ");
		    test.delete();
		}
	}
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

import java.util.*;

import java.lang.*;

import java.io.*;

class Heap <T extends Comparable<T> > {

//arraylist is much better than an array. There is no need to carry about a capacity.

private ArrayList<T> items;

//construct

public Heap() {

items = new ArrayList<T> ();

}

//using shiftUp for insert.

private void shiftUp () {

int k = items.size() - 1;

while (k > 0){

int curr = (k-1)/2;

T Item = items.get(k);

T Parent = items.get(curr);

if (Item.compareTo(Parent) > 0){

items.set(k, Parent);

items.set(curr, Item);

k = curr;

}

else break;

}

//using shiftDown fo delete

private void shiftDown() {

int curr = 0;

int leftChild = 2*curr+1;

while (leftChild < items.size()) {

int max = leftChild;

int rightChild = leftChild + 1;

if (rightChild < items.size()) {

if (items.get(rightChild).compareTo(items.get(1)) > 0) {

++max;

}

if (items.get(curr).compareTo(items.get(max)) < 0) {

T tmp = items.get(curr);

items.set(curr, items.get(max));

items.set(max, tmp);

curr = max;

leftChild = 2*curr+1;

}

else break;

}

public void insert(T item) {

items.add(item);

shiftUp();

}

public T delete() throws NoSuchElementException {

if (items.size() == 0) {

throw new NoSuchElementException();

}

if (items.size() == 1) return items.remove(0);

T x = items.get(0);

items.set(0, items.remove(items.size()-1));

shiftDown();

return x;

}

public int size() {

return items.size();

}

public boolean isEmpty() {

return items.isEmpty();

}

public String toString() {

return items.toString();

}

public T max() {

return items.get(0);

}

public void print() {

for (int i = 0; i < items.size(); i++) {

System.out.print(items.get(i).toString() + " ");

}

System.out.println();

}

class Codechef {

public static void main (String[] args) {

Heap <Integer> test = new Heap<Integer> ();

test.insert(16);

test.insert(9);

test.insert(11);

test.insert(10);

test.insert(13);

test.insert(31);

test.insert(19);

test.insert(2);

test.insert(50);

test.insert(23);

test.print();

//To kill some hares in the same time:

//- isEmpty() works;

// max() and toString() too

// so does delete() => shiftDown() works;

// heapsort :D

for (;!test.isEmpty();) {

System.out.print(test.max().toString() + " ");

test.delete();

}

java@Cat

Учебные материалы по изучению основ языка програvмирования Java

Tag Archives: Куча

Binary Heap (двоичная куча)

Двоичная куча

Описание методов

О реализации

Код