- // get parent
- UInt nextIndex = currentIndex / heap->arity;
- Real nextValue = ((ItemValue*)(heap->array->datas[nextIndex]))->value;
- // compare to parent (if applicable)
- if (currentIndex == 0 ||
- (heap->hType == MIN_T && startItemValue->value >= nextValue) ||
- (heap->hType == MAX_T && startItemValue->value <= nextValue))
+ bool land = (currentIndex == 0), //at root: can't go up
+ applyExchange = true;
+ if (!land)
+ {
+ // Get parent and compare to it
+ UInt nextIndex = (currentIndex - 1) / heap->arity;
+ Real nextValue = *((Real*)(_vector_get(heap->values, nextIndex)));
+ land = (
+ (heap->hType == MIN_T && startValue >= nextValue) ||
+ (heap->hType == MAX_T && startValue <= nextValue)
+ );
+ if (!land)
+ {
+ // Move one level up: the parent goes one level down
+ if (currentIndex == startIndex)
+ {
+ // Save startItem (because *startItem is about to be changed)
+ void* newStartItem = safe_malloc(heap->items->dataSize);
+ memcpy(newStartItem, startItem, heap->items->dataSize);
+ startItem = newStartItem;
+ startItemReallocated = true;
+ }
+ void* nextItem = _vector_get(heap->items, nextIndex);
+ _vector_set(heap->items, currentIndex, nextItem);
+ _vector_set(heap->values, currentIndex, &nextValue);
+ currentIndex = nextIndex;
+ continue;
+ }
+ // At correct relative place: will now land
+ if (currentIndex == startIndex)
+ applyExchange = false;
+ }
+ if (applyExchange)