Стек наиболее часто встречающихся элементов

Сложная

hard , heap , hash table

03 June 2024

Описание задачи #

Необходимо реализовать структуру данных, которая позволит сохранять и доставать целочисленные элементы. Для этого необходимо реализовать 3 функции:

Constructor() FreqStack конструктор, инициализирующий структуры данных.
FreqStack.Push(val int) метод структуры данных, позволяющий сохранить целочисленный элемент внутрь структуры данных FreqStack
FreqStack.Pop() int метод структуры данных, удаляющий и возвращающий элемент из структуры данных, по следующему принципу:

Если в FreqStack существует элемент, который встречается чаще остальных, из стек извлекается этот элемент (последний добавленный из серии).
Если в FreqStack существуют несколько наборов элементов с одинаковой частотой, извлекается элемент из того набора, чей элемент был добавлен а FreqStack последним.
Если в FreqStack все элементы имеют одинаковую частоту/все элементы встречаются только 1 раз, элемент извлекается по принципу стека.

Ограничения #

Добавляемые/извлекаемые элементы лежат в диапазоне от 0 до 1 000 000 000
Максимальное количество вызовов функций Push и Pop - 20 000
Гарантируется, что перед вызовом функции Pop в FreqStack будет как минимум один элемент

Примеры #

Инициализация:
```
stack := Constructor()

stack.Push(5)
stack.Push(7)
stack.Push(5)
stack.Push(7)
stack.Push(4)
stack.Push(5)
```
Извлечение:
```
stack.Pop() // 5
stack.Pop() // 7
stack.Pop() // 5
stack.Pop() // 4
```
Объяснение:
1. Первым извлекается элемент 5, так как он самый частотный в стеке. При этом извлекается та 5, которая была добавлена последней (по принципу стека)
2. Вторым извлекается элемент 7, так как в стеке оба элемента 5 и 7 встречаются по 2 раза, но последняя 7 была добавлена позже, чем последняя 5 (5, которую мы добавили последним Push'ом мы извлекли первым вызовом Pop)
3. Третьим элементом извлекается элемент 5, так как теперь это самый частотный эоемент в стеке
4. Четвертым извлекается элемент 4, так как теперь в стеке все элементы имеют одинаковую частоту (каждый элемент встречается один раз), а элемент 4 был добавлен в стек последним

Решение #

Реализуемая структура данных очень похожа на классическую задачу из мира практической разработки — Priority Queue. Однако в нашем случае в качестве приоритета выступает частота объекта, а алгоритмом извлечения является стек (LIFO), а не очередь (FIFO).

Подобно Priority Queue, одной из наиболее оптимальных структур данных для реализации будет Heap (куча).

Свойства кучи: #

Каждый узел имеет значение ключа больше/меньше (в зависимости от того, реализуем ли мы Max-кучу или Min-кучу) или равно значению ключей своих потомков.
Куча является почти полным бинарным деревом. Это означает, что все уровни дерева полностью заполнены, кроме, возможно, последнего уровня, который заполняется слева направо.

Реализация кучи с помощью массива #

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

Родительский элемент узла с индексом i находится по индексу (i - 1) / 2.
Левый потомок узла с индексом i находится по индексу 2 * i + 1.
Правый потомок узла с индексом i находится по индексу 2 * i + 2.

Как реализовать требуемую структуру данных #

Для реализации Maximum Frequency Stack нам потребуются следующие структуры данных:

type FreqStack struct {
	h        heap
	freqElem map[int]uint16
	curSeq   uint16
}

type heap []*Item

type Item struct {
	freq uint16
	seq  uint16
	val  int
}

FreqStack - основная структура, которую нам требуется реализовать. Она состоит из:

h - куча, реализованная с помощью массива.
freqElem - хеш-мапа, позволяющая определить частоту элемента на момент вставки.
curSeq - текущий максимальный номер элемента (счетчик элементов).

У этой структуры нам необходимо реализвать методы Push(val int) и Pop() int.

Push(val int) #

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

Частота элемента в куче (можем быстро определять с помощью freqElem). При этом нам достаточно знать частоту элемента на момент вставки (не нужно обновлять уже вставленные элементы в кучу и изменять их положение).
Пордковый номер элемента в куче (для определение используется curSeq).

В кучу элемент изначально помещается в самый конец, после запускается рекурсивный процесс "просеивания вверх" элементов кучи, который восстанавливает свойства кучи.

Просеивание вверх элементов в куче (upElement) #

Просеивание вверх используется после вставки нового элемента в кучу. Элемент вставляется в конец массива (последний уровень дерева), и затем он перемещается вверх до тех пор, пока не будет восстановлено свойство кучи.

Алгоритм просеивания вверх:

Найдите родительский элемент для последнего вставленного элемента. Поскольку мы реализовали кучу через массив, родительский элемент будет располагаться в массиве по индексу (i - 1) / 2.
Сравните ключ нового элемента с его родительским узлом. В нашем случае ключ состоит из частоты и порядкового номера. Один элемент будет считаться больше другого, если его частота больше (при условии, что частоты у двух элементов разные), либо если его порядковый номер вставки больше.
Если элемент больше родительского узла, поменяйте их местами.
Повторяйте шаги 2 и 3, пока элемент не окажется на своем месте или не достигнет корня.

Таким образом, общая сложность вставки элемента в кучу определяется сложностью операции просеивания вверх, которая составляет O(log n), так как в худшем случае нам придется пройтись вверх по бинарному дереву до корневого элемента.

Pop() int #

При извлечении элемента нам необходимо уменьшить частоту этого элемента, а также извлечь его из кучи.

Благодаря свойствам кучи необходимый для вставки элемент всегда будет находится в корне (в нашем случае в массиве под индексом 0). Аналогично с процессом добавления нового элемента, после извлечения корневого элемента из кучи, нам необходимо запустить процесс "просеивания вниз" элементов кучи, который восстанавливает свойства кучи.

Для этого:

Последний элемент кучи перемещается на первое место. Таким образом мы избегаем необходимость сдвигать все элементы кучи на один элемент влево.
Родительский элемент сравнивается с дочерними
Если элемент меньше одного из дочерних узлов, наибольший из дочерних элементов меняется местами с родительским.
Повторяйте шаги 2 и 3, пока элемент не окажется на своем месте или не достигнет последнего уровня дерева.

Аналогично с процессом вставки, сложность процесса извлечения составляет O(log n).

Реализация #

package maximum_frequency_stack

type FreqStack struct {
	h        heap
	freqElem map[int]uint16
	curSeq   uint16
}

func Constructor() FreqStack {
	return FreqStack{
		h:        make(heap, 0),
		freqElem: make(map[int]uint16),
	}
}

func (fs *FreqStack) Push(val int) {
	fs.curSeq++
	fs.freqElem[val]++
	fs.h.add(&Item{
		freq: fs.freqElem[val],
		seq:  fs.curSeq,
		val:  val,
	})
}

func (fs *FreqStack) Pop() int {
	item := fs.h.pop()
	fs.freqElem[item.val]--
	if fs.freqElem[item.val] == 0 {
		delete(fs.freqElem, item.val)
	}

	return item.val
}

type Item struct {
	freq uint16
	seq  uint16
	val  int
}

func (i *Item) more(second *Item) bool {
	if i.freq != second.freq {
		return i.freq > second.freq
	}

	return i.seq > second.seq
}

type heap []*Item

func (h *heap) add(new *Item) {
	*h = append(*h, new)
	h.upElement(len(*h) - 1)
}

func (h *heap) pop() *Item {
	if len(*h) == 0 {
		return nil
	}

	res := (*h)[0]
	if len(*h) > 0 {
		(*h)[0] = (*h)[len(*h)-1]
		*h = (*h)[:len(*h)-1]
		h.heapify(0, len(*h)-1)
	}

	return res
}

func (h *heap) heapify(elemIdx, limit int) {
	left := elemIdx*2 + 1
	if left > limit {
		return
	}
	larger := elemIdx

	if (*h)[left].more((*h)[larger]) {
		larger = left
	}
	right := left + 1
	if right <= limit && (*h)[right].more((*h)[larger]) {
		larger = right
	}

	if larger != elemIdx {
		(*h)[larger], (*h)[elemIdx] = (*h)[elemIdx], (*h)[larger]
		h.heapify(larger, limit)
	}

}

func (h *heap) upElement(elemIdx int) {
	rootIdx := (elemIdx - 1) / 2

	if rootIdx >= 0 && (*h)[elemIdx].more((*h)[rootIdx]) {
		(*h)[rootIdx], (*h)[elemIdx] = (*h)[elemIdx], (*h)[rootIdx]
		h.upElement(rootIdx)
	}
}

class Item {
    freq: number;
    seq: number;
    val: number;

    constructor(freq: number, seq: number, val: number) {
        this.freq = freq;
        this.seq = seq;
        this.val = val;
    }

    more(second: Item): boolean {
        if (this.freq !== second.freq) {
            return this.freq > second.freq;
        }
        return this.seq > second.seq;
    }
}

class Heap {
    items: Item[] = [];

    add(newItem: Item): void {
        this.items.push(newItem);
        this.upElement(this.items.length - 1);
    }

    pop(): Item | null {
        if (this.items.length === 0) {
            return null;
        }

        const res = this.items[0];
        if (this.items.length > 1) {
            this.items[0] = this.items.pop()!;
            this.heapify(0);
        } else {
            this.items.pop();
        }

        return res;
    }

    private heapify(index: number): void {
        const left = index * 2 + 1;
        const right = left + 1;
        let largest = index;

        if (left < this.items.length && this.items[left].more(this.items[largest])) {
            largest = left;
        }
        if (right < this.items.length && this.items[right].more(this.items[largest])) {
            largest = right;
        }

        if (largest !== index) {
            [this.items[index], this.items[largest]] = [this.items[largest], this.items[index]];
            this.heapify(largest);
        }
    }

    private upElement(index: number): void {
        const parent = Math.floor((index - 1) / 2);

        if (parent >= 0 && this.items[index].more(this.items[parent])) {
            [this.items[index], this.items[parent]] = [this.items[parent], this.items[index]];
            this.upElement(parent);
        }
    }
}

export class FreqStack {
    private h: Heap;
    private freqElem: Map<number, number>;
    private curSeq: number;

    constructor() {
        this.h = new Heap();
        this.freqElem = new Map();
        this.curSeq = 0;
    }

    push(val: number): void {
        this.curSeq++;
        this.freqElem.set(val, (this.freqElem.get(val) || 0) + 1);
        this.h.add(new Item(this.freqElem.get(val)!, this.curSeq, val));
    }

    pop(): number {
        const item = this.h.pop();
        if (item) {
            this.freqElem.set(item.val, this.freqElem.get(item.val)! - 1);
            if (this.freqElem.get(item.val) === 0) {
                this.freqElem.delete(item.val);
            }
            return item.val;
        }
        return -1; // or throw an error
    }
}

Оценка сложности #

По времени

Процесс вставки и извлечения элементов в куче составляет O(log n), так как в обоих процессах нам необходимо запускать рекурсивный процесс "просеивания", который идет вверх п одереву от листового элемента (в случае просеивания вверх), либо вниз от корневого элемента до листового (в случае просеивания вниз).

По памяти

Доп память в данном случае составляет O(n), так как мы используем дополнительную хеш-мапу freqElem. Размер данной хеш-мапы в худшем случае равен количеству вставленных элементов.

Оригинал задачи на Leetcode

Algorithmics