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

22/12/2015 by marchelaphil

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

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

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

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

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

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

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

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

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

Сложность: [latex]O(\log(n))[/latex]

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

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

Сложность: [latex]O(1)[/latex]

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

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

Сложность: [latex]O(\log(n))[/latex]

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

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

Сложность: [latex]O(n\log(n))[/latex]

О реализации

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

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

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();

}

soundEx algorithm

20/12/2015 by marchelaphil

Немного о фонетических алгоритмах

Фонетические алгоритмы — алгоритмы, которые сопоставляют двум словам со схожим произношением одинаковые коды, что позволяет осуществлять сравнение и индексацию множества таких слов на основе их фонетического сходства. Существует достаточно много фонетических алгоритмов, например: NYSIIS, Metaphone, Double Metaphone, Caverphone и т.д. В данном отчёте я напишу об одном из фонетических алгоритмов, который называется soundEx.
soundEx — алгоритм, который был разработан Робертом Расселом и Маргарет Кинг Оделл в 10-х годах прошлого века. В основном, этот алгоритм стал известен после того, как был опубликован в книге Дональда Кнута «Искусство программирования».

soundEx

Пример:

Код	Слово
a500	ammonium
i514	implementation

Данным алгоритмом предусмотрено сопоставление индекса вида LNNN(Q123) слову. Этот код получают следуя следующему алгоритму:

Первая буква сохраняется
Все гласные звуки + буквы h, w отбрасываются
Оставшиеся буквы заменяются цифрами в диапазоне от 1 до 6 по следующим правилам:

B, P, F, V 1

C, S, K, G, J, Q, X, Z 2

D, T 3

L 4

M, N 5

R 6
Последовательность из одинаковых цифр заменяется одной такой цифрой
Полученная строка обрезается до первых 4-х символов. Если в строке меньше 4х, то в конец добавляются нули.

Пример:

javalanguage → jvlngg → j214522 → j21452 → j214

Реализация:

Реализация soundEx приводится по выше описанному алгоритму.
Для тестирования создадим HashMap, в котором по ключу-индексу soundEx будем создавать список слов, подходящих под этот ключ.

import java.util.*;
import java.lang.*;
import java.io.*;

class Codechef {
	public static String soundEx (String a){
		int n = a.length();
		char [] sdx = a.toUpperCase().toCharArray();
		char fl = sdx[0];
		for (int i = 0 ; i < n; i++){
			switch(sdx[i]) {
				case 'B' :
				case 'P' :
				case 'F' :
				case 'V' :
					sdx[i] = '1';
					break;
				case 'C':
				case 'S':
				case 'K':
				case 'G':
				case 'J':
				case 'Q':
				case 'X':
				case 'Z':
					sdx[i] = '2';
					break;
				case 'D':
				case 'T':
					sdx[i] = '3';
					break;
				case 'L':
					sdx[i] = '4';
					break;
				case 'M':
				case 'N':
					sdx[i] = '5';
					break;
				case 'R' :
					sdx[i] = '6';
					break;
				default: 
					sdx[i] = '0';
					break;
			}
		}
		String retSdx = "" + fl;
		for (int i = 0; i < sdx.length; i++){
			if (sdx[i] != '0') {
				retSdx += sdx[i];
			}
		}
		String ans = ""+fl;
		for (int i = 1; i < retSdx.length(); i++){
			if (retSdx.charAt(i) != (retSdx.charAt(i-1))) {
				ans += retSdx.charAt(i);
			}
		}
		ans = ans + "0000";
		return ans.substring(0, 4);
	}
	public static void main (String[] args) {
		Map <String, List<String> > words = new HashMap<String, List<String> > ();
		Scanner in = new Scanner (System.in);
		String input = in.nextLine();
		input = " " + input;
		String [] t = input.split(" ");
		for (int i = 1; i < t.length; i++) {
			List<String> L = words.get(soundEx(t[i]));
	    	if (L == null)
				words.put(soundEx(t[i]), L=new ArrayList<String>());
			L.add(t[i]);
		}
		for (Object x : words.keySet()){
			System.out.print(x + ": ");
			List<String> L = words.get(x);
			for (Object y : L) System.out.print(y + " ");
			System.out.println();
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Codechef {

public static String soundEx (String a){

int n = a.length();

char [] sdx = a.toUpperCase().toCharArray();

char fl = sdx[0];

for (int i = 0 ; i < n; i++){

switch(sdx[i]) {

case 'B' :

case 'P' :

case 'F' :

case 'V' :

sdx[i] = '1';

break;

case 'C':

case 'S':

case 'K':

case 'G':

case 'J':

case 'Q':

case 'X':

case 'Z':

sdx[i] = '2';

break;

case 'D':

case 'T':

sdx[i] = '3';

break;

case 'L':

sdx[i] = '4';

break;

case 'M':

case 'N':

sdx[i] = '5';

break;

case 'R' :

sdx[i] = '6';

break;

default:

sdx[i] = '0';

break;

}

String retSdx = "" + fl;

for (int i = 0; i < sdx.length; i++){

if (sdx[i] != '0') {

retSdx += sdx[i];

}

String ans = ""+fl;

for (int i = 1; i < retSdx.length(); i++){

if (retSdx.charAt(i) != (retSdx.charAt(i-1))) {

ans += retSdx.charAt(i);

}

ans = ans + "0000";

return ans.substring(0, 4);

}

public static void main (String[] args) {

Map <String, List<String> > words = new HashMap<String, List<String> > ();

Scanner in = new Scanner (System.in);

String input = in.nextLine();

input = " " + input;

String [] t = input.split(" ");

for (int i = 1; i < t.length; i++) {

List<String> L = words.get(soundEx(t[i]));

if (L == null)

words.put(soundEx(t[i]), L=new ArrayList<String>());

L.add(t[i]);

}

for (Object x : words.keySet()){

System.out.print(x + ": ");

List<String> L = words.get(x);

for (Object y : L) System.out.print(y + " ");

System.out.println();

}

Ссылка на Ideone

Пример:

In: Dedlovskiy Dedlovskih Nasimov Nagimov Zazimov Azazimov Marchenko Merchenko Dedlovich Nagiev Houston Watson
Out:
N521: Nagiev
D341: Dedlovskiy Dedlovskih Dedlovich
A251: Azazimov
M562: Marchenko Merchenko
W325: Watson
Z251: Zazimov
H235: Houston
N525: Nasimov Nagimov

java@Cat

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

Author Archives: marchelaphil

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

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

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

О реализации

Код

soundEx algorithm

Немного о фонетических алгоритмах

soundEx

Пример:

Реализация:

Пример: