Ziele Untersuchung
mit Columbo Integrität von
Datenbanken Interaktion und
Portierbarkeit Ergonomie der
Schnittstellen

Angebot Produkte Projekt Beratung

Mittel Analytik Modellierung Sprachen Algebra Logik Hardware Denken Kreativität

Zusammenhänge Gesellschaft Wirtschaft Branche Firma


products/sources/formale Sprachen/GAP/pkg/datastructures/src/ (Algebra von RWTH Aachen Version 4.15.1^©) Datei vom 14.9.2025 mit Größe 4 kB

Quelle binaryheap.c Sprache: C

//
// Datastructures: GAP package providing common datastructures.
//
// Copyright (C) 2015-2017  The datastructures team.
// For list of the team members, please refer to the COPYRIGHT file.
//
// This package is licensed under the GPL 2 or later, please refer
// to the COPYRIGHT.md and LICENSE files for details.
//
// Implementation of a binary heap.
//
// Binary heaps are of course pretty standard data structures.
// However, a few design choices are possible. The implementation
// below has been influenced by this StackOverflow answer:
//   <https://stackoverflow.com/questions/6531543>
//

#include "binaryheap.h"

#define DS_BINARYHEAP_ISLESS(heap) ELM_PLIST(heap, 1)
#define DS_BINARYHEAP_DATA(heap) ELM_PLIST(heap, 2)

// "Bubble-up" helper used for insertion: Given a heap <data> (represented by
// a GAP plist), and a comparison operation <isLess>, insert the <elm> at
// position <i>. Then compare it to its parent; if they are in the right
// order,
// stop; otherwise, swap them, and repeat the process, now with the new parent
// of our object, until we reach the root.
//
// In practice, we actually only insert the element as the very last step,
// and don't perform actual swaps. That's a simple optimization.
//
// Note that for normal insertions into the heap, as performed by
// DS_BinaryHeap_Insert(), <i> will be equal to the length of <data> plus 1.
// But in DS_BinaryHeap_ReplaceMax(), it can be less than that.
static void DS_BinaryHeap_BubbleUp(Obj data, Obj isLess, Int i, Obj elm)
{
    const Int useLt = (isLess == LtOper);

    if (LEN_PLIST(data) < i) {
        GROW_PLIST(data, i);
        SET_LEN_PLIST(data, i);
    }

    while (i > 1) {
        Obj parent = ELM_PLIST(data, i >> 1);
        if (useLt) {
            if (0 == LT(parent, elm))
                break;
        }
        else {
            if (False == CALL_2ARGS(isLess, parent, elm))
                break;
        }
        SET_ELM_PLIST(data, i, parent);
        i >>= 1;
    }

    SET_ELM_PLIST(data, i, elm);
    CHANGED_BAG(data);
}

// "Bubble down" helper used for extraction: Given a heap <data> (represented
// by a GAP plist), and a comparison operation <isLess>, start with a "hole"
// or "bubble" at position <i>, and push it down through the heap.
static Int DS_BinaryHeap_BubbleDown(Obj data, Obj isLess, Int i)
{
    const Int useLt = (isLess == LtOper);
    const Int len = LEN_PLIST(data);

    while (2 * i <= len) {
        // get positions of the children of <i>
        Int left = 2 * i;
        Int right = 2 * i + 1;

        // if there is no right child, move the left child up
        // and exit
        if (right > len) {
            SET_ELM_PLIST(data, i, ELM_PLIST(data, left));
            i = left;
            break;    // next iteration would stop anyway
        }

        // otherwise, compare left and right child, and move the larger one up
        Obj leftObj = ELM_PLIST(data, left);
        Obj rightObj = ELM_PLIST(data, right);
        if (useLt ? LT(rightObj, leftObj)
                  : (True == CALL_2ARGS(isLess, rightObj, leftObj))) {
            SET_ELM_PLIST(data, i, leftObj);
            i = left;
        }
        else {
            SET_ELM_PLIST(data, i, rightObj);
            i = right;
        }
    }

    return i;
}

static Obj FuncDS_BinaryHeap_Insert(Obj self, Obj heap, Obj elm)
{
    Obj data = DS_BINARYHEAP_DATA(heap);
    Obj isLess = DS_BINARYHEAP_ISLESS(heap);

    if (!IS_DENSE_PLIST(data))
        ErrorQuit(" is not a dense plist", 0L, 0L);

    Int len = LEN_PLIST(data);
    if (len == 0) {
        AssPlist(data, 1, elm);
        RetypeBag(data, T_PLIST_DENSE);
    }
    else {
        DS_BinaryHeap_BubbleUp(data, isLess, len + 1, elm);
    }
    return 0;
}

static Obj FuncDS_BinaryHeap_ReplaceMax(Obj self, Obj heap, Obj elm)
{
    Obj data = DS_BINARYHEAP_DATA(heap);
    Obj isLess = DS_BINARYHEAP_ISLESS(heap);

    if (!IS_DENSE_PLIST(data))
        ErrorQuit(" is not a dense plist", 0L, 0L);

    // treat the head slot as a hole that we move down into a leaf
    Int i = DS_BinaryHeap_BubbleDown(data, isLess, 1);

    // insert the new element into the leaf-hole and move it up
    DS_BinaryHeap_BubbleUp(data, isLess, i, elm);

    return 0;
}

static StructGVarFunc GVarFuncs[] = {
    GVAR_FUNC_2ARGS(DS_BinaryHeap_Insert, heap, elm),
    GVAR_FUNC_2ARGS(DS_BinaryHeap_ReplaceMax, heap, elm),
    { 0 }
};

static Int InitKernel(void)
{
    InitHdlrFuncsFromTable(GVarFuncs);
    return 0;
}

static Int InitLibrary(void)
{
    InitGVarFuncsFromTable(GVarFuncs);
    return 0;
}

struct DatastructuresModule BinaryHeapModule = {
    .initKernel = InitKernel, .initLibrary = InitLibrary,
};

quality78%

¤ Dauer der Verarbeitung: 0.12 Sekunden (vorverarbeitet) ¤

Wurzel

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.