- 01
- 02
- 03
- 04
- 05
- 06
- 07
- 08
- 09
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
#include <stdio.h>
#define XORSWAP(a, b) ((a)^=(b),(b)^=(a),(a)^=(b))
static int heap_size;
int parent(int i){
return i >> 1;
}
int left(int i){
return i << 1;
}
int right(int i){
return (i << 1) | 0x1;
}
void heapify(int *h, int i){
int l = left(i);
int r = right(i);
int largest;
if(l <= heap_size && h[l] > h[i])
largest = l;
else
largest = i;
if(r <= heap_size && h[r] > h[largest])
largest = r;
if(largest != i){
XORSWAP(h[i], h[largest]);
heapify(h, largest);
}
}
void make_heap(int *h, int len){
int i;
heap_size = len;
for(i = len/2; i >= 1; i--)
heapify(h, i);
}
int main(int argc, char *argv[]){
int i;
int h[11] = {0, 1, 3, 5, 7, 9, 2, 4, 6, 8, 10};
make_heap(h, 11);
for(i = 1; i < 11; i++)
printf((i + 1 == 11) ? "%d" : "%d ", h[i]);
return 0;
}
Follow us!
Только вроде она должна быть с линейной сложностью, а тут что-то непонятное.
Но похоже что у ОПа все нормально. Т.е. это только кажется что сложность выше.
> XORSWAP
Нинужно. Делай нормальный свап в виде функции и не выябывайся знанием макросов и битовой магии.
> heap_size
Почему у тебя размер массива в глобалке? Передай его параметром.
> l <= heap_size
> for(i = 1; i < 11; i++)
Это залёт... за границу массива. В си массивы с нуля. Ну и все parent/child и .тп. у тебя тоже написаны для массивов с единицы.
> for(i = len/2; i >= 1; i--)
Деление пополам там точно нужно? Я не уверен, но вроде надо было все ноды окучивать.
P.S. Лабы на ГК не постят.
И тогда не получится сделать хиккерскую магию здесь: return (i << 1) | 0x1;
У Кормена индексы тоже с единицы для общности, а у Левитина они с единицы сознательно, хотя все его псевдокоды заточены под си. Нулевой элемент не используется.
И да, это не лаба. Посоветуйте, где можно посмотреть профессиональную реализацию структур в реальных проектах. Гуглится одно только лабное говно с убогим, негибким интерфейсом.
Ну окей, окей, уговорил. Только один хер за границу вылетаешь. Нету в этом массиве 11-го элемента.
И навсегда забыть о тредах (можно в тредлокал засунуть, но это тот ещё костыль).
> либо передавать как параметр
Либо положить и указатель и длину в структуру и таскать их всегда вместе.
Ты ему так очень тонко предлагаешь уйти в С++ же?
Ну не сделаешь ты на чистой сишке гибкий интерфейс. Смирись. Не знаю, что именно ты хочешь гибкого. Но если функцию, работающую с произвольными типами - то в итоге всё выльется в void* обёрнутый в какое-нибудь макроговно, или в memcpy или во вложенную структуру и container_of.
А что это? :) Ну ок, проект для самообучения основам алгоритмов и проектирования. По сути та же лаба, только сдаёшь себе вместо препода.
Везде говорят, что иногда требуется писать структуры данных с нуля типа расширений красно-черных деревьев для нахождения порядковых статистик. На деле написать их не так сложно, как сделать их пригодными для использования.
- состояние твоего контейнера загоняешь в структуру
- указатель на структуру передаешь во все "методы"
- ...
- профит
> Куча
> Профессиональная структура данных
/0
Обычно от неё толку, что с козла - молока. Оно вроде и есть, но никто его не пьет.
И почему среди алгоритмов кучи, нет реализации для кучи как структуры данных на основе дерева через линки поинтеров, должно быстрее вставляться в такую кучу
Для прикладных целей есть std::priority_queue. Зачем тебе нужна голая куча как контейнер? А если heap sort на её основе мутить - контейнер вместо алгоритма вообще палки в колёса будет вставлять.
> на основе дерева
Да ну... Памяти жрёт больше, хуёво кешируется, дрочит аллокатор на каждый чих (последние 2 пункта вроде как пофиксятся кастомным аллокатором)... Ну и скатывание элемента один фиг будет править кучу линков по дороге. Так что если элементы мелкие - можно и в проигрыше остаться.
Проблемы начнутся при вытаскивании же, не при впихивании. У тебя в корне самый большой элемент, ты его выдираешь. Соотв. надо на его место скатить одного из потомков и т.п. Или я туплю?
Use std::multiset, Luke.
Бля, вот я понимаю вашу(си\плюсовиков) любовь к макросам. Но почему тогда либо не все вынести в макросы, либо чуть более по-человечески в функции?