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/gap/ (Algebra von RWTH Aachen Version 4.15.1^©) Datei vom 14.9.2025 mit Größe 2 kB

Quelle binaryheap.gi Sprache: unbekannt

##
##  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.
##

# This file contains a GAP implementation of a binary max-heap.
#
# Some hints for writing efficient binary heap implementations:
# <https://stackoverflow.com/questions/6531543>
#
# Note that while there are other heap datastructures which in
# theory have better asymptotical behavior than binary heaps, in
# real-world applications, a well-tunes binary heap often
# outperforms other heap implementations anyway, due to its
# simplicity, low constant (in O-notation) and cache friendliness.
#

#! @Chapter Heaps
#! @Section Binary Heaps
InstallGlobalFunction(BinaryHeap,
function(arg...)
    local isLess, data, heap, x;

    isLess := \<;
    data := [];

    if Length(arg) = 1 then
        if IsFunction(arg[1]) then
            isLess := arg[1];
        else
            data := arg[1];
        fi;
    elif Length(arg) = 2 then
        isLess := arg[1];
        data := arg[2];
    elif Length(arg) > 2 then
        Error("Wrong number of arguments");
    fi;

    heap := Objectify( BinaryHeapType, [ isLess, [] ] );

    for x in data do
        DS_BinaryHeap_Insert(heap, x);
    od;
    return heap;
end);

InstallMethod(Push,
    "for a binary heap in plain representation",
    [IsBinaryHeapFlatRep, IsObject],
    DS_BinaryHeap_Insert);

InstallMethod(Pop,
    "for a binary heap in plain representation",
    [IsBinaryHeapFlatRep],
function(heap)
    local val, data;
    data := heap![2];

    if Length(data) = 0 then
        return fail; # alternative: error
    elif Length(data) = 1 then
        return Remove(data);
    fi;

    val := data[1];
    DS_BinaryHeap_ReplaceMax(heap, Remove(data));
    return val;
end);

InstallMethod(Peek,
    "for a binary heap in plain representation",
    [IsBinaryHeapFlatRep],
function(heap)
    if Length(heap![2]) = 0 then
        return fail; # alternative: error
    fi;
    return heap![2][1];
end);

InstallOtherMethod(Size,
    "for a binary heap in plain representation",
    [IsBinaryHeapFlatRep],
    heap -> Length(heap![2]));

InstallOtherMethod(IsEmpty,
    "for a binary heap in plain representation",
    [IsBinaryHeapFlatRep],
    heap -> Length(heap![2]) = 0);

InstallMethod(ViewString,
    "for a binary heap in flat representation",
    [IsBinaryHeapFlatRep],
function(heap)
    return STRINGIFY("<binary heap with ", Length(heap![2]), " entries>");
end);