Первая страница / Теория / Разное /

Кучи

Голосование: 24, 4

Введение

Области применения

Кучи являются основной структурой данных во многих приложениях. В том числе, они применяются:

  • при сортировке элементов;
  • в алгоритмах выбора, для поиска минимума и/или максимума, медианы;
  • в алгоритмах на графах, в частности, при построении минимального остовного дерева алгоритмом Крускала (Joseph Kruskal), при нахождении кратчайшего пути алгоритмом Дейкстры (Edsger W. Dijkstra).

Свойства и операции на кучах

В общем случае куча представляет собой одно или несколько деревьев с явно выделенными корнями, элементы хранятся в вершинах. Основное свойство кучи (heap order): ключ каждой вершины не меньше, чем ключ её родителя. В дальнейшем корень дерева T будем обозначать как root(T), а значение ключа в вершине t как value(t).

Основными операциями на кучах можно считать:

  • MAKE(x) - создание кучи из элемента x;
  • INSERT(x, h) - добавление нового элемента x в кучу h;
  • MELD(h1, h2) - слияние куч h1 и h2;
  • FIND-MIN(h) - поиск минимального элемента в куче h;
  • DELETE-MIN(h) - удаление минимального элемента из кучи h;
  • DECREASE(x, h, y) - замена ключа x на меньший ключ y в куче h;
  • DELETE(x, h) - удаление произвольного элемента x из кучи h.
Этот список нельзя назвать исчерпывающим, так как в некоторых приложениях могут потребоваться какие-то иные операции, которые в реализации могут использовать данные, а могут быть и независимыми.

Кучи, основанные на двоичных деревьях

Будем рассматривать кучи, основанные на двоичных деревьях. Родителя вершины t будем обозначать как parent(t), правого ребенка - right(t), а левого - left(t). Основываясь на свойстве кучи можно сделать вывод, что минимальный элемент всегда будет находиться в корне. Правым путем (right-path) от вершины t назовем путь до листа дерева, проходящий лишь по ребрам, ведущим к правым детям.

Binary Heaps

Назовем бинарное дерево Binary кучей ([1]), если оно обладает свойством кучи и заполнено на всех уровнях, кроме последнего, где оно заполнено слева направо. Тогда такую кучу будет удобно хранить в виде массива элементов h[0..n]: если t = h[i], то left(t) = h[i * 2 + 1], right(t) = h[i * 2 + 2], а parent(t) = h[(i - 1) / 2].

Пример Binary кучи
Рис.1. Пример Binary кучи

Введем две дополнительные операции, которые будут восстанавливать нарушенное свойство кучи у вершины t - просеивание вверх (sift-up) и просеивание вниз (sift-down):

SIFT-UP(t)
1: while value(parent(t)) > value(t) do
2:     value(t) ↔ value(parent(t))
3:     t ← parent(t)
SIFT-DOWN(t)
1: while min != t do
2:     mint
3:     if value(left(t)) < value(min) then
4:         min ← left(t)
5:     if value(right(t)) < value(min) then
6:         min ← right(t)
7:     value(min) ↔ value(t)
8:     mint

Теперь можно описать основные операции:

INSERT(x, h)
1: Добавляем новый элемент на последний уровень
2: Восстанавливаем свойство кучи, путем проведения операции SIFT-UP для вновь добавленного элемента
DELETE-MIN(h)
1: Устанавливаем значение в корне равным значению в самом правом элементе на последнем уровне, после чего удаляем этот элемент
2: Восстанавливаем свойство кучи, путем проведения операции SIFT-DOWN для первого элемента
DECREASE(x, h, y)
1: value(x) = y
2: Восстанавливаем свойство кучи, путем проведения операции SIFT-UP для измененного элемента i

Leftist Heaps (C.A. Crane, 1972 [2])

Рангом (rank) бинарного дерева T назовем длину правого пути от корня до листа и будем обозначать как rank(T).

Назовем бинарное дерево Leftist, если для каждого его поддерева T выполняется Leftist условие: rank(left(T)) >= rank(right(T)). Бинарное дерево с вышеприведенными операциями является Leftist кучей, если оно удовлетворяет свойству кучи и Leftist условию.

Пример Leftist кучи с указанием рангов вершин
Рис.2. Пример Leftist кучи с указанием рангов вершин

Операции добавления элемента и удаления минимального можно выразить через операцию слияния:

INSERT(x, h)
1: return MELD(x, h)
DELETE-MIN(h)
1: return MELD(left(h), right(h))

Таким образом, нам осталось лишь корректно ввести операцию слияния двух Leftist куч (т.е. так, чтобы она не нарушала Leftist условия):

MELD(h1, h2)
1: if value(h1) >= value(h2) then make(left(h1), value(h1), merge(right(h1), h2))
2:                           else make(left(h2), value(h2), merge(h1, right(h2)))
MAKE(h1, v, h2)
1: if rank(h1) >= rank(h2) then Node(rank(h2) + 1, h1, v, h2)
2:                         else Node(rank(h1) + 1, h2, v, h1)

Реализацию основных операций и ряд дополнительных над Leftist кучами на Haskell можно найти в статье [3].

Skew Heaps (Daniel D.Sleator and Robert E.Tarjan, 1986 [4])

Top-down Skew Heaps

Постараемся модифицировать Leftist кучи и избавиться от необходимости хранить и пересчитывать ранги, т.е. от Leftist условия. Такое представление получило название нисходящих (Top-down) Skew куч.

Пример Top-down Skew кучи
Рис.3. Пример Top-down Skew кучи

Слияние куч будем производить путем слияния их правых путей аналогично слиянию двух упорядоченных списков. При этом необходимо менять местами левых и правых детей у элементов на результирующем пути:

MELD(h1, h2)
1: if h1 == null then return h2
2: if value(h1) > value(h2) then h1h2
3: left(h1), right(h2) ← MELD(right(h1), h2), left(h1)
4: return h1

Представленный выше рекурсивный алгоритм слияния можно перезаписать в итеративной форме:

MELD(h1, h2)
1: if value(h1) > value(h2) then h1h2
2: x, y, h1, right(h1) ← h1, h1, right(h1), left(h1)
3: while h1 != null do
4:     if h1 > h2 then h1h2
5:     y, left(y), h1, right(h2) ← h1, h1, right(h1), left(h1)
6: left(y) ← h1
7: return x

Bottom-up Skew Heaps

В некоторых задачах, таких как MST, например, требуется большая эффективность операции слияния. Поэтому немного видоизменим наше представление кучи: родителя вершины t будем обозначать как up(t) (указатель наверх). А down(t) (указатель вниз) будем обозначать наименьшую вершину в правом пути левого поддерева вершины t. Если левое поддерево пусто, то down(t) = t. В силу того, что корень дерева t не имеет родителя: up(root(t)) будем обозначать наименьшую вершину в правом пути. Такое представление Skew куч называется восходящим (Bottom-up). Назовем главным путем (major path) путь снизу вверх от up(root(T)) до root(T), а дополнительным путем (minor path) путь от down(root(T)) до root(T). В приведенном примере элементы 15, 17 и 19 лежат на главном пути, а элементы 15, 18 и 20 на дополнительном.

Пример Bottom-up Skew кучи
Рис.4. Пример Bottom-up Skew кучи.

Операцию слияния куч будем производить путем слияния главных путей аналогично нисходящему представлению, но уже снизу вверх:

MELD(h1, h2)
1: if up(h1) < up(h2) then h1h2
2: h3 ← up(h1); up(h1) ← up(h3); up(h3) ← h3;
3: while h1 != h3
4:     if up(h1) < up(h2) then h1h2
5:     x ← up(h1); up(h1) ← up(x);
6:     up(x) ← down(x); down(x) ← up(h3); h3 ← up(h3) ← x
7: up(h2) ↔ up(h3);
8: return h2

Так как наше представление кучи не дает возможности получить непосредственный доступ к детям корня (узла, который будет удален), чтобы модифицировать их указатели наверх, то удаление минимального элемента будем производить путем слияния главного и дополнительного путей кучи:

DELETE-MIN(h)
1: y1, y2 ← up(h), down(h)
2: if y1 = h and y2 = h then return null
3: if value(y1) <= value(y2) then y1y2
4: h3y1; y1 ← up(y1); up(h3) ← h3;
5: while true
6:     if value(y1) < value(y2) then y1y2
7:     if y1 = h then return h3
8:     xy1; y1 ← up(y1);
9:     up(x) ← down(x); down(x) ← up(h3); h3 ← up(h3) ← x;

Другие кучи

В данной статье не рассматриваются Биномиальные (Binomial) и Фибоначчиевы (Fibonacci) кучи. Их подробное описание можно найти в [8].

Pairing Heaps (Michael L.Fredman, Robert Sedgewick, Daniel D.Sleator and Robert E.Tarjan, 1986 [5] [6])

Произвольное дерево с выделенным корнем является Pairing кучей, если оно удовлетворяет свойству кучи.

Пример Pairing кучи
Рис.5. Пример Pairing кучи
Основываясь на нем, введем следующие операции:

FIND-MIN(h)
1: return value(h)
INSERT(x, h)
1: return MELD(x, h)
MELD(h1, h2)
1: if value(h1) < value(h2) then h1h2
2: подвешиваем дерево h1 как самый левый ребенок к дереву h2
3: return h2
DELETE(x, h)
1: if x = root(h) then
2:     return DELETE-MIN(h)
3: Отсоединяем от кучи поддерево с корнем x
4: return MELD(DELETE-MIN(x), h)
DECREASE(x, h, y)
1: if h = x then
2:     value(h) = y
3:     return h
4: Отсоединяем от кучи поддерево с корнем x
5: value(x) = y
6: return MELD(x, h)

Рассмотрим операцию удаления минимального элемента. Он является корнем дерева, а следовательно после его удаления у нас остается некоторое число деревьев (т. е. детей удаленного корня). Pairing кучи различаются по этой операции как двухпроходные (two pass) и многопроходные (multi pass):

DELETE-MIN(h)
1: Делается проход слева направо, при этом сливаются пары деревьев.
2: Делается проход справа налево, при этом мы сливаем получившиеся деревья в одно результирующее, по одному.
DELETE-MIN(h)
1: Все деревья складываются в очередь.
2: Пока в очереди есть хотя бы два элемента
3:     извлекаем их, сливаем и получившееся дерево кладем  в очередь.
4: Результирующим деревом будет являться единственное, оставшееся в очереди

2-3 Heaps (Tadao Takaoka, 1999 [7])

2-3 кучи были разработаны как альтернатива фибоначчиевым кучам. При большом количестве последовательных операций добавления Фибоначчиева куча растет в ширину и балансировка происходит лишь при операции удаления минимума, поэтому операция получения минимума может потребовать значительных затрат времени. А в 2-3 кучах балансировка происходит при любых операциях добавления и удаления элементов.

Количество детей вершины t произвольного дерева T назовем степенью (degree) этой вершины, а степенью дерева назовем степень его корня.

2-3 деревьями называются деревья T0, T1, T2, ..., определенные индуктивно. Дерево T0 состоит из единственной вершины. Под деревом Ti понимается дерево, составленное либо из двух деревьев Ti-1 либо из трех: при этом корень каждого следующего становится самым правым ребенком корня предыдущего (рис.6).

Структура 2-3 деревьев
Рис.6. Структура 2-3 деревьев

Деревьями 2-3 кучи назовем деревья H[i]. Дерево H[i] - это либо пустое 2-3 дерево, либо одно, либо два 2-3 дерева степени i, соединенные аналогично деревьям Ti.

2-3 куча - это массив деревьев H[i] (i=0..n), для каждого из которых выполняется свойство кучи.

Добавление элемента

Для добавления нового элемента создадим дерево H[0] содержащее одну вершину и произведем операцию добавления этого дерева в кучу. При добавлении дерева степени i в кучу возможны следующие варианты:

  1. в куче уже существует дерево степени i, тогда извлечем его и соединим с добавляемым (рис.7), после чего добавим полученные деревья
  2. в куче нет дерева степени i, поэтому просто поместим его в кучу

Слияние деревьев
Рис.7. Слияние деревьев

Удаление минимального элемента

Минимальный элемент кучи находится в корне одного из деревьев кучи, допустим в H[i]. Извлечем дерево H[i] из кучи и удалим его корень, при этом дерево распадется на поддеревья, которые мы впоследствии добавим в кучу.

Будем удалять корень рекурсивно: если дерево состоит из одной вершины, то просто удалим её; иначе отсоединяем от корня самого правого ребенка и продолжим удаление (рис.8).

Удаление корня
Рис.8. Удаление корня

Soft Heaps (B. Chazelle, 2000 [9])

Soft куча является довольно интересной структурой данных - приближенной очередью с приоритетами. Изначально она была разработана для алгоритма нахождения минимального остовного дерева, предложенного Чазелом (Bernard Chazelle) [10]. Так же она имеет и иные применения такие как, например: нахождение медиан за линейное время, приближенная сортировка.

Особенность Soft кучи заключается в том, что она может в любое время увеличить размер определенных ключей. Такие ключи и соответствующие им элементы назовем поврежденными. В действительности при поиске минимального элемента мы будем получать элементы с минимальным текущим (не настоящим) ключом. Параметр E (error rate) (0 < E < 1/2) контролирует количество повреждений. При любой последовательности операций, включающей в себя n операций добавления, Soft куча будет содержать в себе не более n*E поврежденных элементов.

Описание структуры

Биномиальными деревьями (binomial trees) называются деревья с порядком на детях B0, B1, B2, ..., определяемые индуктивно. Дерево В0 состоит из единственной вершины. Дерево Bk склеено из двух экземпляров дерева Bk-1: корень одного из них объявлен самым правым ребёнком корня другого.

Soft очередь (Soft Queue) q - это биномиальное дерево с возможно отсутствующими поддеревьями. Биномиальное дерево, из которого получено q назовем главным деревом. Рангом q назовем степень его главного дерева и обозначим как rank(q). Введем условие ранга (rank invariant): если q - корень, то число детей q не должно быть меньше чем rank(q)/2.

Вершина v может содержать более одного значения, а точнее - целый список значений. Значение ckey - текущий ключ (current key) определяет общее текущее (возможно поврежденное) значение всех ключей в этом списке и является верхней границей всех неповрежденных ключей. В очереди поддерживается порядок кучи по отношению к текущим ключам. Зафиксируем целый параметр r = 2+2*log(1/E) и будем требовать, чтобы все поврежденные элементы находились в вершинах, чей ранг больше r.

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

Две очереди ранга 2 соединяются в очередь ранга 3, вершины ниже 6 и 9 отсутствуют. Вершины упорядочены в соответствии с текущими ключами, а не с изначальными.
Рис.9. Две очереди ранга 2 соединяются в очередь ранга 3, вершины ниже 6 и 9 отсутствуют. Вершины упорядочены в соответствии с текущими ключами, а не с изначальными.

Структура для ключей, хранящихся в каждой вершине, представляет собой список и включает в себя значение ключа и указатель на следующий элемент:

class IlCell {
    int key;
    IlCell next = null;
}

Каждая запись Soft очереди содержит указатель на список ключей, общее текущее значение ключа и ранг очереди. Указатели next и child указывают на записи очередей меньшего ранга, из которых состоит очередь.

class Node {
    int  ckey = 0;
    int rank = 0;
    Node next = null, child = null;
    IlCell il = null;
    IlCell il_tail = null;
}

Основная структура кучи - это двусвязный список голов (head-list). Каждый его элемент содержит в себе ссылку на очередь, ранг, а так же минимальную ссылку. Минимальная ссылка - это указатель на голову (возможно на данную) с наименьшим ключом в корне очереди, среди всех голов лежащих после данной в списке.

class Head {
    Node quenue;
    Head next, prev, suffix_min;
    int rank;
}

При инициализации кучи мы создаем две фиктивные головы:

header = new Head(); 
tail = new Head();
tail.rank = INF; 
header.next = tail;
tail.prev = header;

Добавление элемента

Чтобы добавить новый элемент, мы создаем неповрежденную очередь из одного элемента, после чего сливаем её с исходной кучей.

Добавление дерева

Мы хотим добавить дерево в кучу. Вначале мы просматриваем список голов до позиции, с которой мы можем начать. Ранг очереди в этой позиции должен быть не меньше чем у q (дерева, которое мы добавляем).

void meld(Node q) {
    Head h, prevhead, tohead = header.next;
    Node top, bottom;
    while (q.rank > tohead.rank) tohead = tohead.next;
    prevhead = tohead.prev;

Если у нас уже присутствует дерево такого же ранга что и q, мы соединяем эти два дерева и получаем дерево с рангом на единицу большим:

    while (q.rank == tohead.rank) {
        if (tohead.quenue.ckey > q.ckey) {
            top = q; bottom = tohead.quenue;
        } else {
            top = tohead.quenue; bottom = q;
        }
        q = new Node();
        q.ckey = top.ckey; 
        q.rank = top.rank + 1;
        q.child = bottom; q.next = top;
        q.il = top.il;  q.il_tail = top.il_tail;
        tohead = tohead.next;
    }   /* End of while */

Теперь мы готовы вставить наше дерево в список голов:

    if (prevhead == tohead.prev) h = new Head();
    else h = prevhead.next;
    h.quenue = q; h.rank = q.rank;
    h.prev = prevhead; h.next = tohead;
    prevhead.next = h; tohead.prev = h;

В конце мы вызываем функцию, которая корректирует минимальные ссылки с позиции h до начала списка голов:

    fixMinlist(h);
}

void fixMinlist(Head h) {
    Head tmpmin;
    if (h.next == tail) tmpmin = h;
    else tmpmin = h.next.suffix_min;
    while (h != header) {
        if (h.quenue.ckey < tmpmin.quenue.ckey)
            tmpmin = h;
        h.suffix_min = tmpmin;
        h = h.prev;
    }
}

Удаление минимума

Минимальная ссылка у первого элемента списка голов всегда указывает на очередь с минимальной записью (возможно поврежденной). Проблема заключается в том, что запись может оказаться пустой, тогда мы должны пополнить запись из дочерних элементов. Для этого мы введем функцию просеивания - sift(h).

Функция удаления минимума возвращает элемент с минимальным значением ckey и удаляет его из кучи.

int deletemin() {
    Node tmp;
    int min, childcount;
    Head h = header.next.suffix_min;
    while (h.quenue.il == null) {
        tmp = h.quenue; childcount = 0;
        while (tmp.next != null) 
            {tmp = tmp.next; childcount++;}

Если нарушается условие ранга, мы просто удаляем очередь и обновляем минимальные ссылки. После чего просто снова вставляем всех детей в кучу:

        if (childcount < h.rank / 2) {
            h.prev.next = h.next; h.next.prev = h.prev;
            fixMinlist(h.prev);
            tmp = h.quenue;
            while (tmp.next != null) {
                meld(tmp.child);
                tmp = tmp.next;
            }

Если условие ранга выполняется, мы просто вызываем sift:

        } else {
            h.quenue = sift(h.quenue);
            if (h.quenue.ckey == INF) {
                h.prev.next = h.next;
                h.next.prev = h.prev;
                h = h.prev;
            }
            fixMinlist(h);
        }
        h = header.next.suffix_min;
    }

Теперь мы можем удалить минимальный элемент:

    min = h.quenue.il.key;
    h.quenue.il = h.quenue.il.next;
    if (h.quenue.il == null) h.quenue.il_tail = null;
    return min;
}
Node sift(Node v) {
    Node tmp = null;
    v.il = null; v.il_tail = null;
    if (v.next == null && v.child == null) {
        v.ckey = INF; return v;
    }
    v.next = sift(v.next); 

Очередь v.next теперь может имеет больший ckey, что нарушает порядок. В таком случае мы меняем местами ссылки children v.next и v.child.

    if (v.next.ckey > v.child.ckey) {
        tmp = v.child;
        v.child = v.next;
        v.next = tmp;
    }

Копируем элементы содержащиеся в меньшей куче.

    v.il = v.next.il;
    v.il_tail = v.next.il_tail;
    v.ckey = v.next.ckey;

В следующей строке содержится главная особенность soft heap - возможность просеиванию выполнятся дважды.

    if (v.rank > r && (v.rank % 2 == 1 || v.child.rank < v.rank - 1)) {
        v.next = sift(v.next);

В результате нам может снова понадобится восстановить порядок.

    if (v.next.ckey > v.child.ckey) {
        tmp = v.child;
        v.child = v.next;
        v.next = tmp;
    }

Все элементы, содержащиеся в v.next, должны объединится с элементами, содержащимися в v.

    if (v.next.ckey != INF && v.next.il != null) {
        v.next.il_tail.next = v.il;
        v.il = v.next.il;
        if (v.il_tail == null) v.il_tail = v.next.il_tail;
        v.ckey = v.next.ckey;
    }

Очищаем очередь, удаляя записи с ключами бесконечность.

    if (v.child.ckey == INF) {
        if (v.next.ckey == INF) {
            v.child = null; v.next = null;
        } else {
            v.child = v.next.child;
            v.next = v.next.next;
        }
    }
    return v;
}

Оценки времени работы

Сводная таблица амортизированного времени работы:

Операция Binary Leftist Top-Down Skew Bottom-Up Skew Pairing Binomial Fibonacci 2-3 Soft
MAKE O(1) O(1) O(1) O(1) O(1) O(1) O(1) O(1) O(1)
INSERT O(log N) O(log N) O(log N) O(1) O(log N) * O(log N) O(1) O(1) O(log 1/E)
MELD O(N) O(log N) O(log N) O(1) O(log N) * O(log N) O(1) O(log N) O(1)
FIND-MIN O(1) O(1) O(1) O(1) O(1) O(log N) O(1) O(1) O(1)
DELETE-MIN O(log N) O(log N) O(log N) O(log N) O(log N) O(log N) O(log N) O(log N) O(1)
DECREASE O(log N) O(log N) O(log N) O(log N) O(log N) * O(log N) O(1) O(1) O(1)
DELETE O(log N) O(log N) O(log N) O(log N) O(log N) O(log N) O(log N) O(log N) O(1)

* Для Pairing куч операции добавления элемента, уменьшения ключа и слияния гипотетически выполняются за время O(1), но данная оценка еще не доказана.

Литература

  1. Kevin Wayne.   Theory of Algorithms. — Princeton University (2002).
  2. C.A. Crane.   Linear lists and priority queues as balanced binary trees. — Computer Science Dept, Stanford Univ. (1972).
  3. Lyn Turbak.   Leftist Heaps. — Wellesley College, Handout #32a (2001).
  4. Daniel D.Sleator and Robert E.Tarjan.   Self-Adjusting Heaps. — SIAM J. Computing, 15 (1986).
  5. Michael L.Fredman, Robert Sedgewick, Daniel D.Sleator and Robert E.Tarjan.   The Pairing Heap: A New Form of Self-Adjusting Heap. — Algorithmica (1986).
  6. Sartaj Sahni.   Pairing Heaps. — Data Structures, Algorithms, & Applications in Java (1999).
  7. Tadao Takaoka.   Theory of 2-3 Heaps. — Cocoon (1999).
  8. Кормен Т., Лейзерсон Ч., Ривест Р.  Алгоритмы: построение и анализ. — М.: МЦНМО, 2001. — С. 376-409.
  9. B. Chazelle.   The Soft Heap: An Approximate Priority Queue with Optimal Error Rate. — Journal of the ACM, 47 (2000), 1012-1027.
  10. B. Chazelle.   A Minimum Spanning Tree Algorithm with Inverse-Ackermann Type Complexity. — Journal of the ACM, 47 (2000), 1028-1047.

Визуализаторы

  1. Мандриков E. Binary, Leftist and Skew heaps. — 2006.
  2. Курбацкий Е. Pairing heaps. — 2006.
  3. Билык В. Binomial heaps. — 2001.
  4. Колыхматов И. Fibonacci heaps. — 2005.
  5. Курбацкий Е. 2-3 heaps. — 2006.
  6. Курбацкий Е. Soft heaps. — 2006.

Мандриков и Курбацкий Евгении Андреевичи


Marcin Ciura / 2007-04-03 20:43:52

Здравствуйте. Простите ошибки в моем писании по-русски -- давно не практиковал.

В вашем описании bottom-up skew кучи и в ее визуализаторе ошибка. Она обнаружилась уже в 1987 г. в статье Джонса A note on bottom-up skew heaps, SIAM J. Comput. 16(1): 108-110.

Чтобы ее увидеть, запустите визуализатор, во-первых удалите из кучи все элементы кроме 9 и 10, добавите 10 и удалите минимум (9). Должна получиться двух-элементная куча с корнем 10 и левым его сыном 10. Теперь удалите минимальный элемент - удаляются оба элемента!

Чтобы исправить алгоритм, надо например выбросить линейку 3 и добавить линейку 1,5: if y1=h and y2=h then return null.

Спасибо за Ваше замечание. Надеемся, автор статьи и визуализатора внесет рекомендуемые исправления.

...

P.S. Автор устранил указанные ошибки. Исправленные версии выложены на сайт 16.05.2007.

Ваше имя
Email
Текущий день недели (строчными буквами)
Комментарий