Geek Answers Handbook

Is a heap an abstract data type?

I take the Data-Structure course and got a little confused about what is considered ADT (abstract data type) and what is not (and if it is not ADT, then should it be an implementation?).

In particular, I'm talking about a heap.

I read on Wikipedia that “heap is a specialized tree-based data structure” does this mean that it is an ADT? if so, then I can’t understand the next line, also from Wikipedia “A heap is the most efficient implementation of an abstract data type called a priority queue”.

I mean, can Heap be an ADT, and also be an implementation of some other ADT (in this case, the implementation of the priority queue? I understand the concept of ADT and in the context of Binary Heap, I understand that it can be implemented using an array, where arr[i]is the parent element arr[2i]and arr[2i + 1] I just got confused about whether the heap can be in one ADT hand, which is implemented using an array, and on the other hand, a data structure that implements another ADT.

I would like some clarification on this subject.

+7
source share
5 answers

The heap is not an ADT. This is a data structure.

Mandatory quote from Wikipedia:

(ADT) , () , , , . , , , .

-, Code Complete -2.

, ADT, . ADT , . , node , , .

  • , , ​​ insert(), heapify(), peek(), getTop() .. - . , .

  • , Tetris, , , Tetris ADT.

+6

. wikipedia :

, . - "" ""; , , , .

, (ADT), , :

  • (BST)
  • (AVL-)
  • ( OP)

Priority Queue ADT :

----------------------------------------------------------------------------
| Implementation | Insertion   | Deletion(DeleteMax/DeleteMin)|Find Max/Min
----------------------------------------------------------------------------
| Unordered Array| 1           | n                            | n
----------------------------------------------------------------------------
| Unordered List | 1           | n                            | n
----------------------------------------------------------------------------
| Ordered Array  | n           | 1                            | 1
----------------------------------------------------------------------------
| Ordered List   | n           | 1                            | 1
----------------------------------------------------------------------------
| BST            | logn (avg.) | logn (avg.)                  | logn (avg.)
----------------------------------------------------------------------------
| Balanced BST   | log n       | log n                        | log n
----------------------------------------------------------------------------
| Binary Heaps   | log n       | log n                        | 1
+2

, , . , , .

- , , "", , . ,

,

"", , .

- (DS) ADT.priority ADT

,

, - .

, , ( ADT), ADT, . DS.

:

" - "

, DS, ADT.

+1

1) Java, [ , ]

(ADT) - , . , . , , .

2) , 4-

, , .

, :

3) Wikipead:

Basic

    find-max (or find-min): find a maximum item of a max-heap, or a minimum item of a min-heap, respectively (a.k.a. peek)
    insert: adding a new key to the heap (a.k.a., push[4])
    extract-max (or extract-min): returns the node of maximum value from a max heap [or minimum value from a min heap] after removing it from the heap (a.k.a., pop[5])
    delete-max (or delete-min): removing the root node of a max heap (or min heap), respectively
    replace: pop root and push a new key. More efficient than pop followed by push, since only need to balance once, not twice, and appropriate for fixed-size heaps.[6]

Creation

    create-heap: create an empty heap
    heapify: create a heap out of given array of elements
    merge (union): joining two heaps to form a valid new heap containing all the elements of both, preserving the original heaps.
    meld: joining two heaps to form a valid new heap containing all the elements of both, destroying the original heaps.

Inspection

    size: return the number of items in the heap.
    is-empty: return true if the heap is empty, false otherwise.

Internal

    increase-key or decrease-key: updating a key within a max- or min-heap, respectively
    delete: delete an arbitrary node (followed by moving last node and sifting to maintain heap)
    sift-up: move a node up in the tree, as long as needed; used to restore heap condition after insertion. Called "sift" because node moves up the tree until it reaches the correct level, as in a sieve.
    sift-down: move a node down in the tree, similar to sift-up; used to restore heap condition after deletion or replacement.

, ADT, - , , ADT

, 1 2 , 3 ADT , , . ,

Java Software Structures [ , ] HeapADT

public interface HeapADT<T> extends BinaryTreeADT<T>
{
/**
* Adds the specified object to this heap.
*
* @param obj the element to be added to this heap
*/
public void addElement (T obj);
/**
* Removes element with the lowest value from this heap.
*
* @return the element with the lowest value from this heap
*/
public T removeMin();
/**
* Returns a reference to the element with the lowest value in
* this heap.
*
* @return a reference to the element with the lowest value in this heap
*/
public T findMin();
}

, 4- PriorityQueue ADT:

public class MaxPQ< Key extends Comparable<Key>> 
MaxPQ() create a priority 
queueMaxPQ(int max) create a priority queue of initial capacity max 
MaxPQ(Key[] a) create a priority queue from the keys in a[]
void  insert(Key v) insert a key into the priority queueKey  
max() return the largest keyKey  
delMax() return and remove the largest key  
boolean isEmpty() is the priority queue empty?
int  size() number of keys in the priority queue

DS: https://algs4.cs.princeton.edu/24pq/MaxPQ.java.html

, :

- , .

:

, ( ) .

, List List adt, List, ADT , .

: C++ . . , . . ( )

, , -, , ADT, , , DS.

:

& Java

-

+1

More articles:


All Articles