Double Ended Priority Queue (DEPQ)
A double-ended priority queue (DEPQ) or double-ended heap is defined as a data structure like
a priority queue or heap, but permits for efficient removal of both the maximum and minimum,
according to some ordering on the keys or items stored in the structure. Every element in a
DEPQ associated with a priority or value. In a DEPQ, it is possible to eliminate or remove the
elements in both ascending and descending order.
A double ended priority queue supports operations of both max heap (a max priority queue)
and min heap (a min priority queue). The following operations are expected from double ended
priority queue.
1. getMax() : Returns maximum element.
2. getMin() : Returns minimum element.
3. deleteMax() : Deletes maximum element.
4. deleteMin() : Deletes minimum element.
5. size() : Returns count of elements.
6. isEmpty() : Returns true if the queue is empty.
Implementation
// C++ program to implement double-ended
// priority queue using self balancing BST.
#include <bits/stdc++.h>
using namespace std;
struct DblEndedPQ {
set<int> s;
// Returns size of the queue. Works in
// O(1) time
int size()
{
return s.size();
}
// Returns true if queue is empty. Works
// in O(1) time
bool isEmpty()
{
return (s.size() == 0);
}
// Inserts an element. Works in O(Log n)
// time
void insert(int x)
{
s.insert(x);
}
// Returns minimum element. Works in O(1)
// time
int getMin()
{
return *(s.begin());
}
// Returns maximum element. Works in O(1)
// time
int getMax()
{
return *(s.rbegin());
}
// Deletes minimum element. Works in O(Log n)
// time
void deleteMin()
{
if (s.size() == 0)
return;
s.erase(s.begin());
}
// Deletes maximum element. Works in O(Log n)
// time
void deleteMax()
{
if (s.size() == 0)
return;
auto it = s.end();
it--;
s.erase(it);
}
};
// Driver code
int main()
{
DblEndedPQ d;
d.insert(10);
d.insert(50);
d.insert(40);
d.insert(20);
cout << d.getMin() << endl;
cout << d.getMax() << endl;
d.deleteMax();
cout << d.getMax() << endl;
d.deleteMin();
cout << d.getMin() << endl;
return 0;
}
Task:
Implement it using Heaps
Shell Sort
Shell sort is mainly a variation of Insertion Sort. In insertion sort, we move elements only one
position ahead. When an element has to be moved far ahead, many movements are involved. The
idea of ShellSort is to allow the exchange of far items. In Shell sort, we make the array h-sorted
for a large value of h. We keep reducing the value of h until it becomes 1. An array is said to be
h-sorted if all sublists of every h’th element are sorted.
Algorithm:
Step 1 − Start
Step 2 − Initialize the value of gap size. Example: h
Step 3 − Divide the list into smaller sub-part. Each must have equal intervals to h
Step 4 − Sort these sub-lists using insertion sort
Step 5 – Repeat this step 2 until the list is sorted.
Step 6 – Print a sorted list.
Step 7 – Stop.
Pseudocode :
PROCEDURE SHELL_SORT(ARRAY, N)
WHILE GAP < LENGTH(ARRAY) /3 :
GAP = ( INTERVAL * 3 ) + 1
END WHILE LOOP
WHILE GAP > 0 :
FOR (OUTER = GAP; OUTER < LENGTH(ARRAY); OUTER++):
INSERTION_VALUE = ARRAY[OUTER]
INNER = OUTER;
WHILE INNER > GAP-1 AND ARRAY[INNER – GAP] >= INSERTION_VALUE:
ARRAY[INNER] = ARRAY[INNER – GAP]
INNER = INNER – GAP
END WHILE LOOP
ARRAY[INNER] = INSERTION_VALUE
END FOR LOOP
GAP = (GAP -1) /3;
END WHILE LOOP
END SHELL_SORT
Implementation
Following is the implementation of ShellSort.
// C++ implementation of Shell Sort
#include <iostream>
using namespace std;
/* function to sort arr using shellSort */
int shellSort(int arr[], int n)
{
// Start with a big gap, then reduce the gap
for (int gap = n/2; gap > 0; gap /= 2)
{
// Do a gapped insertion sort for this gap size.
// The first gap elements a[0..gap-1] are already in gapped order
// keep adding one more element until the entire array is
// gap sorted
for (int i = gap; i < n; i += 1)
{
// add a[i] to the elements that have been gap sorted
// save a[i] in temp and make a hole at position i
int temp = arr[i];
// shift earlier gap-sorted elements up until the correct
// location for a[i] is found
int j;
for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)
arr[j] = arr[j - gap];
// put temp (the original a[i]) in its correct location
arr[j] = temp;
}
}
return 0;
}
void printArray(int arr[], int n)
{
for (int i=0; i<n; i++)
cout << arr[i] << " "; }
int main()
{
int arr[] = {12, 34, 54, 2, 3}, i;
int n = sizeof(arr)/sizeof(arr[0]);
cout << "Array before sorting: \n";
printArray(arr, n);
shellSort(arr, n);
cout << "\nArray after sorting: \n";
printArray(arr, n);
return 0; }
