| dbpedia-owl:abstract
|
- In der Informatik ist ein Heap (wörtlich Haufen oder Halde) eine zumeist auf Bäumen basierende abstrakte Datenstruktur. In einem Heap können Objekte oder Elemente abgelegt und aus diesem wieder entnommen werden. Sie dienen damit der Speicherung von Mengen. Den Elementen ist dabei ein Schlüssel zugeordnet, der die Priorität der Elemente festlegt. Häufig werden auch die Elemente selbst als Schlüssel verwendet. Über die Menge der Schlüssel muss daher eine totale Ordnung festgelegt sein, über welche die Reihenfolge der eingefügten Elemente festgelegt wird. Beispielsweise könnte die Menge der ganzen Zahlen zusammen mit der Kleinerrelation (<) als Schlüsselmenge fungieren. Der Begriff Heap wird häufig als bedeutungsgleich zu einem partiell geordneten Baum verstanden. Gelegentlich versteht man einschränkend nur eine besondere Implementierungsform eines partiell geordneten Baums, nämlich die Einbettung in ein Array, als Heap. Verwendung finden Heaps vor allem dort, wo es darauf ankommt, schnell ein Element mit höchster Priorität aus dem Heap zu entnehmen, beispielsweise bei Vorrangwarteschlangen.
- In computer science, a heap is a specialized tree-based data structure that satisfies the heap property: if B is a child node of A, then key(A) ≥ key(B). This implies that an element with the greatest key is always in the root node, and so such a heap is sometimes called a max-heap. (Alternatively, if the comparison is reversed, the smallest element is always in the root node, which results in a min-heap. ) There is no restriction as to how many children each node has in a heap, although in practice each node has at most two. The heap is one maximally-efficient implementation of an abstract data type called a priority queue. Heaps are crucial in several efficient graph algorithms such as Dijkstra's algorithm, and in the sorting algorithm heapsort. A heap data structure should not be confused with the heap which is a common name for dynamically allocated memory. The term was originally used only for the data structure. Some early popular languages such as LISP provided dynamic memory allocation using heap data structures, which gave the memory area its name. Heaps are usually implemented in an array, and do not require pointers between elements. The operations commonly performed with a heap are: find-max or find-min: find the maximum item of a max-heap or a minimum item of a min-heap, respectively delete-max or delete-min: removing the root node of a max- or min-heap, respectively increase-key or decrease-key: updating a key within a max- or min-heap, respectively insert: adding a new key to the heap merge: joining two heaps to form a valid new heap containing all the elements of both.
- En computación, un montículo es una estructura de datos del tipo árbol con información perteneciente a un conjunto ordenado. Los montículos máximos tienen la característica de que cada nodo padre tiene un valor mayor que el de todos sus nodos hijos, mientras que en los montículos mínimos, el valor del nodo padre es siempre menor al de sus nodos hijos. Un árbol cumple la condición de montículo si satisface dicha condición y además es un árbol binario completo. Un árbol binario es completo cuando todos los niveles están llenos, con la excepción del último, que se llena desde la izquierda hacia la derecha. En un montículo de prioridad, el mayor elemento (o el menor, dependiendo de la relación de orden escogida) está siempre en el nodo raíz. Por esta razón, los montículos son útiles para implementar colas de prioridad. Una ventaja que poseen los montículos es que, por ser árboles completos, se pueden implementar usando arreglos, lo cual simplifica su codificación y libera al programador del uso de punteros. La eficiencia de las operaciones en los montículos es crucial en diversos algoritmos de recorrido de grafos y de ordenamiento.
- Keko (engl. heap), joskus myös kasa, on tietojenkäsittelytieteessä käytettävä tietorakenne, jolle on ominaista, että sen suurin (tai pienin) alkio on aina helposti saatavilla. Tärkeimpiä keon sovelluskohteita ovat mm. prioriteettijonon toteutus ja kekojärjestäminen.
- Un heap binario, o più semplicemente heap, è una struttura dati interna utilizzata in informatica, più precisamente un vettore o una lista che soddisfi la condizione heap. Un heap può essere visto, per comodità di rappresentazione, come un albero binario quasi completo. È usato principalmente per la memorizzazione di collezioni di dati, dette dizionari, e per la rappresentazione di code di priorità. Esistono due tipi di heap: min-heap e max-heap. La differenza, seppur minima, tra queste due verrà descritta in seguito. La scelta di utilizzare un tipo di heap anziché l'altro è data dal tipo di impiego che se ne vuole fare. Dato j, indice ad un nodo della heap, si definiscono Padre di j il nodo in posizione j/2, Figlio sinistro di j il nodo in posizione j*2 e Figlio destro di j il nodo in posizione j*2+1. Si possono quindi definire le funzioni Padre(j), FiglioSX(j), FiglioDX(j) che rispettivamente restituiscono l'indice del padre, del figlio sinistro e del figlio destro di j. Spesso sono implementate come macro o funzioni in linea. Condizioni Heap: dato j indice di posizione della struttura e v lo heap preso in considerazione se min-heap: v[Padre(j) Padre(j)] < v[j j] se max-heap: v[Padre(j) Padre(j)] > v[j j] Da qui se ne deduce quindi che una min-heap possiede sempre l'elemento minore alla radice, mentre una max-heap possiede sempre l'elemento maggiore alla radice. In ogni nodo è presente una coppia (k,x) in cui k è il valore della chiave associata alla entry x. Nei dizionari, a differenza delle mappe, ogni chiave può essere associata a più entry (come in un "reale" dizionario ogni parola ha più significati). Questi tipi di albero hanno la seguente caratteristica: qualsiasi nodo padre ha chiave minore di entrambi (se esistono) i suoi figli. In questo modo si garantisce che compiendo un qualsiasi percorso che parte da un nodo v dell'albero e scendendo nella struttura verso le foglie, si attraversano nodi con chiave sempre crescente (in senso lato). Nell'immagine a fianco è possibile osservare quanto sopra descritto, in aggiunta si può dire che viene definito come last l'elemento che si trova più a destra nel livello delle foglie. Nell'esempio last assume il valore 15. Questo particolare nodo assume un compito determinante nei metodi per la rimozione della chiave minima (che è ovvio supporre, per le proprietà citate, si trovi nella radice) e nell'inserimento di una nuova chiave.
- ヒープ C言語などにおける動的に確保できるメモリ領域としての「ヒープ領域」については、リンク先を参照。 木構造の一つ。下記参照。 ヒープ（Heap）は、木構造の一つ。単に「ヒープ」という場合、二分木を使った二分ヒープを指すことが多いため、そちらを参照すること。
- Een heap is een abstracte datastructuur in de informatica, niet te verwarren met een zogenaamd heapgeheugen. Een heap is een array-datastructuur die een binaire boom representeert. Een array A is een heap als deze voldoet aan de heapvoorwaarde: als B een kind van A is, dan sleutel(A) ≥ sleutel(B).
- Heap (norsk haug) er en datastruktur brukt i informatikk, mye brukt til å lage prioritetskø og for å sortere data. En haug lagrer data i et tre (datastruktur). Ethvert element E er koblet til «barn», som skal ha en verdi lik eller mindre enn E. Dette sikrer at roten i treet vil være det største i datamengden, og at leting etter høyeste verdi tar O(1) tid. Leting etter vilkårlig verdi blant de N som ligger i haugen, tar derimot O(N) tid, da det ikke er klart hvor i haugen nye element legges. En haug kan også brukes til det motsatte, der hvert element E peker til barn som er høyere enn seg E. Altså vil roten da være det minste i mengden. De fleste programmeringsspråk har ferdige hjelpemidler for å ta i bruk haug.
- Kopiec (ang. heap, tłumaczone też jako stóg lub sterta) – w informatyce struktura danych oparta na drzewie, w której wartości potomków węzła są w stałej relacji z wartością rodzica (na przykład wartość rodzica jest nie mniejsza niż wartości jego potomka).
- Um heap é uma estrutura de dados organizada como árvore binária, seguindo algumas regras.
- En heap eller partiellt ordnat vänsterbalanserat träd är en datastruktur, närmare bestämt ett träd, som karakteriseras av att varje nods värde är större eller lika med värdena i nodens barn (partiellt ordnat). trädets grenar är så lika långa som möjligt. I fall det inte är möjligt så fylls den nedersta nivån på från vänster (vänsterbalanserat). Detta kallas ibland för en max-heap, alternativt kan man implementera en heap så att varje nods värde är mindre eller lika med nodens barns värden, en sådan heap kallas min-heap. Namnet heap kommer från att det faktum att trädet är vänsterbalanserat gör det implementerbart i ett sammanhängande minnesområde, till exempel en minnesheap eller array. Nivå k i ett träd där varje nod har b barn, räknat med roten som 0, har noder. Första noden på nivån har position indexerat från 0. Alltså går det att räkna ut var i minnet en viss nod finns lagrad, om trädet har minst så många noder. Detta i kombination med partiell ordning gör operationen att upprepade gånger "plocka" det största talet ur trädet billig, samtidigt som nya element och uppdateringar är effektiva. Den är därför lämplig som exempelvis prioritetskö för jobb.
- 在计算机科学中，堆是一种经过排序的树形数据结构，每个结点都有一个值。通常我们所说的堆的数据结构，是指二叉堆。堆的特点是根结点的值最小（或最大），且根结点的两个子树也是一个堆。 由于堆的这个特性，常用来实现优先队列，并用于一些图论算法中。 堆也用于排序算法，如堆排序。 Template:计算机小作品
- В компьютерных науках ку́ча — это специализированная структура данных типа дерево, которая удовлетворяет свойству кучи: если B является узлом-потомком узла A, то ключ(A) ≥ ключ(B). Из этого следует, что элемент с наибольшим ключом всегда является корневым узлом кучи, поэтому иногда такие кучи называют max-кучами (в качестве альтернативы, если сравнение перевернуть, то наименьший элемент будет всегда корневым узлом, такие кучи называют min-кучами). Не существует никаких ограничений относительно того, сколько узлов-потомков имеет каждый узел кучи, хотя на практике их число обычно не более двух. Куча является максимально эффективной реализацией абстрактного типа данных, который называется очередью с приоритетом. Кучи имеют решающее значение в некоторых эффективных алгоритмах на графах, таких как алгоритм Дейкстры и сортировка методом пирамиды. Структуру данных куча не следует путать с понятием куча в динамическом распределении памяти. Впервые термин использовался именно для структур данных. В некоторых ранних популярных языках программирования типа ЛИСП обеспечивалось динамическое распределение памяти с использованием структуры данных «куча», которая и дала своё имя выделяемому объёму памяти.. Кучи обычно реализуются в виде массивов, что исключает наличие указателей между её элементами. Над кучами обычно проводятся следующие операции: найти максимум или найти минимум: найти максимальный элемент в max-куче или минимальный элемент в min-куче, соответственно удалить максимум или удалить минимум: удалить корневой узел в max- или min-куче, соответственно увеличить ключ или уменьшить ключ: обновить ключ в max- или min-куче, соответственно добавить: добавление нового ключа в кучу. слияние: соединение двух куч с целью создания новой кучи, содержащей все элементы обеих исходных.
- Fichier:Tas tableau arbre 002. png Un exemple de tas En informatique, un tas, en anglais Modèle:Lang, (ou plus précisément un tas binaire) est une structure de données répondant aux conditions suivantes : c'est un arbre binaire complet il est ordonné en tas
|
| rdfs:comment
|
- Keko (engl. heap), joskus myös kasa, on tietojenkäsittelytieteessä käytettävä tietorakenne, jolle on ominaista, että sen suurin (tai pienin) alkio on aina helposti saatavilla. Tärkeimpiä keon sovelluskohteita ovat mm. prioriteettijonon toteutus ja kekojärjestäminen.
- ヒープ C言語などにおける動的に確保できるメモリ領域としての「ヒープ領域」については、リンク先を参照。 木構造の一つ。下記参照。 ヒープ（Heap）は、木構造の一つ。単に「ヒープ」という場合、二分木を使った二分ヒープを指すことが多いため、そちらを参照すること。
- Een heap is een abstracte datastructuur in de informatica, niet te verwarren met een zogenaamd heapgeheugen. Een heap is een array-datastructuur die een binaire boom representeert. Een array A is een heap als deze voldoet aan de heapvoorwaarde: als B een kind van A is, dan sleutel(A) ≥ sleutel(B).
- Kopiec (ang. heap, tłumaczone też jako stóg lub sterta) – w informatyce struktura danych oparta na drzewie, w której wartości potomków węzła są w stałej relacji z wartością rodzica (na przykład wartość rodzica jest nie mniejsza niż wartości jego potomka).
- Um heap é uma estrutura de dados organizada como árvore binária, seguindo algumas regras.
- 在计算机科学中，堆是一种经过排序的树形数据结构，每个结点都有一个值。通常我们所说的堆的数据结构，是指二叉堆。堆的特点是根结点的值最小（或最大），且根结点的两个子树也是一个堆。 由于堆的这个特性，常用来实现优先队列，并用于一些图论算法中。 堆也用于排序算法，如堆排序。 Template:计算机小作品
- In der Informatik ist ein Heap (wörtlich Haufen oder Halde) eine zumeist auf Bäumen basierende abstrakte Datenstruktur. In einem Heap können Objekte oder Elemente abgelegt und aus diesem wieder entnommen werden. Sie dienen damit der Speicherung von Mengen. Den Elementen ist dabei ein Schlüssel zugeordnet, der die Priorität der Elemente festlegt. Häufig werden auch die Elemente selbst als Schlüssel verwendet.
- In computer science, a heap is a specialized tree-based data structure that satisfies the heap property: if B is a child node of A, then key(A) ≥ key(B). This implies that an element with the greatest key is always in the root node, and so such a heap is sometimes called a max-heap. (Alternatively, if the comparison is reversed, the smallest element is always in the root node, which results in a min-heap.
- En computación, un montículo es una estructura de datos del tipo árbol con información perteneciente a un conjunto ordenado. Los montículos máximos tienen la característica de que cada nodo padre tiene un valor mayor que el de todos sus nodos hijos, mientras que en los montículos mínimos, el valor del nodo padre es siempre menor al de sus nodos hijos. Un árbol cumple la condición de montículo si satisface dicha condición y además es un árbol binario completo.
- Un heap binario, o più semplicemente heap, è una struttura dati interna utilizzata in informatica, più precisamente un vettore o una lista che soddisfi la condizione heap. Un heap può essere visto, per comodità di rappresentazione, come un albero binario quasi completo. È usato principalmente per la memorizzazione di collezioni di dati, dette dizionari, e per la rappresentazione di code di priorità. Esistono due tipi di heap: min-heap e max-heap.
- Heap (norsk haug) er en datastruktur brukt i informatikk, mye brukt til å lage prioritetskø og for å sortere data. En haug lagrer data i et tre (datastruktur). Ethvert element E er koblet til «barn», som skal ha en verdi lik eller mindre enn E. Dette sikrer at roten i treet vil være det største i datamengden, og at leting etter høyeste verdi tar O(1) tid.
- En heap eller partiellt ordnat vänsterbalanserat träd är en datastruktur, närmare bestämt ett träd, som karakteriseras av att varje nods värde är större eller lika med värdena i nodens barn (partiellt ordnat). trädets grenar är så lika långa som möjligt. I fall det inte är möjligt så fylls den nedersta nivån på från vänster (vänsterbalanserat).
- В компьютерных науках ку́ча — это специализированная структура данных типа дерево, которая удовлетворяет свойству кучи: если B является узлом-потомком узла A, то ключ(A) ≥ ключ(B). Из этого следует, что элемент с наибольшим ключом всегда является корневым узлом кучи, поэтому иногда такие кучи называют max-кучами (в качестве альтернативы, если сравнение перевернуть, то наименьший элемент будет всегда корневым узлом, такие кучи называют min-кучами).
- Fichier:Tas tableau arbre 002. png Un exemple de tas En informatique, un tas, en anglais Modèle:Lang, (ou plus précisément un tas binaire) est une structure de données répondant aux conditions suivantes : c'est un arbre binaire complet il est ordonné en tas
|
