1) Java Software Structures,International Edition [John Lewis, Joseph Chase]
An abstract data type (ADT) is a data type whose values and operations
are not inherently defined within a programming language. It is
abstract only in that the details of its implementation must be
defined and should be hidden from the user. A collection, therefore,
is an abstract data type.
2) Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne
Using abstract data types You do not need to know how a data type is implemented in order to be able to use it.
So if you only are designing a behaviour like this:
3) Wikipead heap operations:
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.
Realy this is only an ADT, and the implementation is the Data Structure, in fact, one of the two books defined the heap as ADT
So, by 1 and 2, indicate that 3 can be a ADT of a heap, because you can implementet the heap with an array and with a pointers for example. and the same for the priority queue, but the time complexity can change
In the Java Software Structures,International Edition [John Lewis, Joseph Chase] has the 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();
}
but in Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne has the PriorityQueue as an 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
And as a DS: https://algs4.cs.princeton.edu/24pq/MaxPQ.java.html
And I think that they only say this:
The binary heap is a data structure that can efficiently support the
basic priority-queue operations. In a binary heap, the keys
Because they are talk about the implementation:
are stored in an array such that each key is guaranteed to be
larger than (or equal to) the keys at two other specific positions.
Another example could be say, about List, List could be an adt and static array and dinamic array are the data structures to implement a List, but another authors define the ADT to, because is the expected behaviour.
You can chek this arrays adt in this another book: DATA STRUCTURES IN C++ by N. S. KUTTI, P. Y. PADHYE (you can check here)
So finnaly, if you are defining the behaviour of something I would say that is a ADT, and if you are doing the implementation I would say that is a DS.
Edit:
Another contradiction between books
Data Structures & Algorithms in Java Robert Lafore
A priority queue is a more specialized data structure
